题目描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
- 示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶
- 示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
- 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶
学习文章
思路
递归
动态规划，公式为：f(n)=f(n−1)+f(n−2)
这个其实就是有名的生小兔子：斐波那契数列
斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）第一反应就是递归；退出条件和递推都很明确。
递归（C语言）
int climbStairs(int n) {
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
return (climbStairs(n-1) + climbStairs(n-2));
}
结果应该是对的，但是不符合复杂度要求：
递归解法
滚动数组
递归的好处是理解起来简单，坏处是占用内存太多。递归对应的数据结构是栈。每计算一个，就要将前两个压栈，当n较大的时候，栈空间就用完了。
滚动数组只需要3个存储位置就好了。
原理其实很简单：
计算下一个的时候，当前的f(n-2)已经没用了，可以丢弃。所以通过移动的方式，将当前3个数字往前挪一位，然后计算前2个的和，放入第3个位置就可以了。
- C代码
int climbStairs(int n) {
// 边界条件
if (n == 0) {
return 1;
}
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
// n从3开始就通过滚动计算获得
int target = 2; // f(2) f(n)
int previous1 = 1; // f(1) f(n-1)
int previous2 = 1; // f(0) f(n-2)
// 滚动数组
for (int i = 3; i <= n; i++) {
// 现在f(n-1)就是下个数的f(n-2)
previous2 = previous1;
// 现在f(n)就是下个数的f(n-1)
previous1 = target;
// 执行公式f(n) = f(n-1) + f(n-2)
target = previous1 + previous2;
}
// 返回结果
return target;
}
JS的实现和C基本一样，不用贴了。把int 改为let就好了。当然性能还是10倍以上的差距。
