LeetCode 0070 - Climbing Stairs
# Hints
- DP
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Easy |
You are climbing a stair case. It takes steps to reach to the top.
Each time you can either climb or steps. In how many distinct ways can you climb to the top?
Example 1:
Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Example 2:
Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
Constraints:
# 题意
有一个 级的台阶,每步可以上行 或 级台阶,求上到台阶顶端的方案数。
# 题解
考虑动态规划,设 表示上到第 级台阶的方案数。
状态转移方程:
则 即为答案。时间复杂度为 。
# AC代码
class Solution {
public:
int climbStairs(int n) {
// 初始化
int dp[n + 1];
dp[0] = 1;
dp[1] = 1;
// 递推
for (int i = 2; i <= n; i ++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
// 返回
return dp[n];
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01