算法—爬楼梯

假设你正爬楼梯，需要n阶才能到顶楼。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到顶楼呢？（n 为正整数）

示例0：n = 1 ==>1种方法
示例1：n = 2，1：1阶+1阶； 2：直接爬2阶。==> 2种方法
示例2：n = 3，1：1阶+1阶+1阶； 2：2阶+1阶；3：1阶+2阶。==>3种方法

解析：该问题可以使用动态规划来分解为一些包含最优子结构的问题，即它的最优解可以从其子问题的最优解来有效的构建。

思路：假设先爬n个台阶有f(n)个可能：
1：先爬1阶，剩下n-1阶有f(n-1)种可能；
2：先爬2阶，剩下n-2阶有f(n-2)种可能；
因此爬n阶可以转化为成2种爬n-1问题的和。f(n) = f(n-1)+f(n-2)

f(n) = f(n-1)+f(n-2)

1、动态规划法

int ClimbStairs(int n) {
    if(n==1) return 1;

    int *sum = malloc(sizeof(int)*(n+1));
    sum[0] = 0;
    sum[1] = 1;
    sum[2] = 2;
    
    for (int i = 3; i <= n; i++) {
        sum[i] = sum[i-1] + sum[i-2];
    }
    return sum[n];
}

2、递归法

/*
 方法一:递归求解法
 f(n) = f(n-1) + f(n-2);//递归方程式
 f(1)=1;
 f(2)=2;
 */
int ClimbStairs_1(int n){
    
    if (n<1)  return 0;
    if (n == 1) return 1;
    if (n == 2) return 2;
    
    return ClimbStairs_1(n-1) + ClimbStairs_1(n-2);
}

总结：该题推荐第一种方法。动态规划法时间复杂度O(n)，递归法时间复杂度O(n^2)。
而且一般递归法在LeetCode不容易通过，时间复杂度高。