到底是爬一阶还是爬两阶？
70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入：2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入：3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
解题思路
自顶向下分析，要想爬上 n 阶台阶，由于一次可以爬 1 或 2 阶台阶，所以爬上 n 阶台阶有两种可能：
- 从 n - 1 阶台阶爬 1 阶台阶
- 从 n - 2 阶台阶爬 2 阶台阶
因此问题就可转化为求爬 n - 1 阶台阶和爬 n - 2 阶台阶的方法数，由于这两者相互独立所以相加即可得到爬上 n 阶台阶的方法数。
这是递归的思路，把一个大的问题转化为求解小的问题。
如下图示：
Show me the Code
// c 语言
int climbStairs(int n){
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
return climbStairs(n - 1) + climbStairs(n - 2);
}
运行结果
分析超时原因
从上面的爬上 n 阶台阶的图中，可以看出对于爬 n - 2 阶台阶的方法种数就有两次重叠，这两次重叠我们只需要计算一次就可以了，同理对于爬 n - 3 阶台阶的方法也有重叠的情况，如果这颗递归树继续向下画的话，这种重叠的情况非常多，所以直接使用递归求解，计算了大量的重叠子问题。
记忆化搜索
从上面的分析可知，递归求解存在大量重复计算，有没有方法可以避免呢？答案是有的，可以将之前计算的结果存起来，就可以避免重复的计算了，这就是记忆化搜索。
Show me the Code
// c 语言
int climbStairsHelper(int n, int *memo) {
/* 0 阶或 1 阶台阶只有一种方法 */
if (n == 0 || n == 1) {
return 1;
}
/* memo 中无值则计算一次，否则代表之前已计算过 */
if (memo[n] == 0) {
memo[n] = climbStairsHelper(n - 1, memo) + climbStairsHelper(n - 2, memo);
}
return memo[n];
}
int climbStairs(int n){
int* res = (int *)malloc((n + 1) * sizeof(int));
if (res == NULL) {
return 0;
}
/* res 中的所有值初始化为 0 */
memset(res, 0, (n + 1) * sizeof(int));
return climbStairsHelper(n, res);
}运行结果
动态规划
从上面使用记忆化搜索思想编写的代码的运行结果，可以看出其不会超时了并且其执行的用时还特别短。由于爬上 n 阶台阶的方法数只与爬上 n - 2 阶台阶和爬上 n - 1 阶台阶的方法数相关，所以没有必要再去定义一个dp数组，只需要定义两个变量分别存储爬上 n - 1 阶台阶的方法数和爬上 n - 2 阶台阶的方法数即可。
Show me the Code
// c 语言
int climbStairs(int n){
int a = 1, b = 1;
for (int i = 2; i <= n; ++i) {
b = a + b;
a = b - a;
}
return b;
}运行结果
腾讯云开发者
