力扣(LeetCode)——70. 爬楼梯

一、题目描述

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

二、解题思路

1. 基本思路：记爬 2 个台阶的个数为 k ，该题目可以转化为计算 k = 0，1，2，…，的方案数，例如：k = 0，表示每次只爬一个台阶，方案数为 $C_{n-k}^k=C_n^0=1$ ；k = 1 ，表示有一次是爬两个台阶，其他都是爬一个台阶，方案数就是 $C_{n-k}^k=C_{n-1}^1=n-1$ ，依次类推，总方案数就是 $$\sum _{k=0}^{\frac{n}{2}}{C}_{n-k}^k$$
2. 具体思路：
   • 暴力解：写一个函数计算 $C_n^k=\frac{n(n-1)\cdots (n-k+1)}{k!}$
   • 动态规划：计算 $C_n^k$ 表，其中 $C_n^k=C_{n-1}^{k-1}+c_{n-1}^k$

三、参考代码

3.1 暴力解

时间复杂度：$O(n^2)$
空间复杂度：$O(1)$

数据可能会溢出

// 计算cnk，k 表示爬 2 个楼梯的个数，n 表示楼梯总数 - k
int c(int k,int n){
    long long int a=1,b=1;
    for(int i=0;i<k;i++){
        a*=n-i;
        b*=k-i;
    }
    return a/b;
}

int climbStairs(int n) {
    int sum=0;
    for(int i=0;2*i<=n;i++){
        sum+=c(i,n-i);
    }
    return sum;
}

3.2 动态规划

时间复杂度：$O(n)$
空间复杂度：$O(1)$

const static int max=45;
long c[max+1][max+1];
// dp方法，核心是 c[n][k]=c[n-1][k-1]+c[n-1][k]
void compute_c(){
    for(int i=0;i<=max;i++){  
        c[i][0]=c[i][i]=1;
    }
    for(int n=1;n<=max;n++){
        for(int k=1;k<n;k++){
            c[n][k]=c[n-1][k-1]+c[n-1][k];
        }
    }
}
int climbStairs(int n) {
    int sum=0;
    compute_c();
    for(int i=0;2*i<=n;i++){
        sum+=c[n-i][i];
    }
    return sum;
}