题目
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2 输出：2 解释：有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶
示例 2：
输入：n = 3 输出：3 解释：有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶
思路
爬 0 层和爬 1 层都只有一种情况， 但是爬两层有两种：一次爬一层一共爬两次、一次爬两层一共爬一次，爬三层有三种：一次爬一层一共爬三次、先爬一层再爬两层一共爬两次、先爬两层再爬一层一共爬两次。所以 f(0) = 1, f(1) = 1, f(2) = 2, f(3) = 3, f(4) = 5。规律是 f(n) = f(n-1) + f(n-2)，因为爬到第 n 阶有两种情况，分别是站在第 n-1 阶爬一层和站在第 n-2 阶爬两层，所以就是 f(n-1) 和 f(n-2)的和。
方法一 官方题解的动态规划
时间复杂度O(n)，空间复杂度O(1)，运行用时 0ms，击败100%，内存消耗5.46MB,击败36.61%。
int climbStairs(int n) {
int p = 0, q = 0, r = 1;
for (int i = 1; i <= n; ++i) {
p = q;
q = r;
r = p + q;
}
return r;
}
方法二 快速幂
看不懂也想不到
方法三 通项公式
这个更想不到了
方法四 递归
本质上和方法一相同。直接递归会超时，需要“记忆递归”，下面是题解里的代码。执行用时 0 ms，击败100%，内存消耗 5.8 MB，击败 5.12%. calloc函数会把分配的内存置为0，而 malloc函数不会。
int _climb(int n, int *arr)
{
if (arr[n] != 0 ) return arr[n];
arr[n] = _climb(n-1, arr) + _climb(n-2, arr);
return arr[n];
}
int climbStairs(int n){
//终止情况
if ( n < 0 ) return 0;
if ( n <= 2) return n;
int *arr = (int*)calloc(n+1, sizeof(int));
arr[1] = 1;
arr[2] = 2;
return _climb(n , arr);
}最后记录一下自己写的垃圾代码
int climbStairs(int n) {
if(n == 1)
return 1;
else{
int a = 1;
int b = 1;
int i = 2;
int res = 1;
while(i <= n){
res = a + b;
a = b;
b = res;
i++;
}
return res;
}
}