力扣70 爬楼梯 C语言 动态规划 递归

题目

假设你正在爬楼梯。需要 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;
	}
}