题目描述
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Note: Given n will be a positive integer.
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
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/climbing-stairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解法
这道题是一道简单难度的题目，但是很经典。假设当前是第n级台阶，因为可以迈1步或者2步，所以迈上第n级台阶的方法是迈上第n-1级台阶的方法和迈上第n-2级台阶方法的和。所以显然可以用递归或动态规划法。
递归
根据上述，第n级台阶，都可以递归到第1级台阶和第2级台阶的和。同时，在递归的过程中，我们存下已经计算过的n级台阶的结果，可以快速返回，不用每次都递归到1和2.
代码
int climbStairsInternal(int n, unordered_map<int, int>& cache) {if (n == 0) return 1;if (n <= 2) return n;auto r = cache.find(n);if (r != cache.end()) {return r->second;}int one_step = climbStairsInternal(n - 1, cache);int two_step = climbStairsInternal(n - 2, cache);cache.insert(make_pair(n, one_step + two_step));return one_step + two_step;}int climbStairs(int n) {unordered_map<int, int> cache;if (n == 0) return 1;if (n <= 2) return n;int one_step = climbStairsInternal(n - 1, cache);int two_step = climbStairsInternal(n - 2, cache);return one_step + two_step;}
执行结果
动态规划
根据前面的分析，我们设dp[n]为第n级台阶的方法，则dp[n] = dp[n-1] + dp[n-2], 特殊的dp[0] = 1, dp[1] = 1, dp[2] = 2
代码
int climbStairs(int n) {
vector<int> dp(n + 1, 0);
if (n == 0) return 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];
}