LeetCode 70 爬楼梯(青蛙跳台阶) | ノート

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

动态规划

$f(n)$ 表示爬到第 $n$ 级台阶的方案数，根据题意，最后一步只有两种可能：跨了一级台阶，或者跨了两级台阶。

所以爬 $n$ 级台阶的方案总数是爬到第 $x−1$ 级台阶的方案数和爬到第 $x−2$ 级台阶的方案数的和。

可以列以下动态规划的转移方程：

$f(n)=f(n−1)+f(n−2)$

然后再考虑以下边界条件:

从第 0 级爬到第 0 级只有一种方案， $f(0) = 1$ 。
从第 0 级爬到第 1 级只有一种方案， $f(1) = 1$ 。

根据这两个边界条件再结合转移方程就可以推导出第 $n$ 级台阶的方案数。

递归解法就不写了，下面列出for循环解法和降低空间复杂度解法。


// for循环解法
class Solution {
public:
    int climbStairs(int n) {
        const int N = 1e5 + 10;
    	int dp[N] = {};
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; ++i) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};

// 由于 f(n) 只跟 f(n−1) 和 f(n−2) 有关，所以不需要长度为 n 的数组记录所有的方案数。
// 只需要 p 和 q 两个变量轮着记录就可以了。
class Solution {
public:
    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;
    }
};

时间复杂度：循环执行 $n$ 次，每次花费常数的时间代价，故渐进时间复杂度为 $O(n)$ 。

空间复杂度：这里只用了常数个变量作为辅助空间，故渐进空间复杂度为 $O(1)$ 。

斐波那契数列通项公式

经过观察可以看出来方案数很像斐波那契数列，那么就可以直接用通项公式了。

主意斐波那契数列（0、1、1、2、3、5、8、13、21、34、……）和题目方案数列（1、1、2、3、5、8、13、21、34、……）开始的时候不太一样，所以在用主意斐波那契数列通项公式计算的时候， $n$ 需要加一。

推导过程如下：

根据线性递推数列方程 $f(n)=f(n−1)+f(n−2)$ ，可知道其特征方程为

$x^2=x+1$

解得 $x_1 = {1 + \sqrt{5} \over 2}，x_2 = {1 - \sqrt{5} \over 2}$

则 $f(n) = c_1x_1^n+c_2x_2^n$

因为 $f(1) = f(2) = 1$

所以 $c_1x_1+c_2x_2 = c_1x_1^2+c_2x_2^2 = 1$

解得 $c_1 = {1 \over \sqrt{5}}，c_2 = -{1 \over \sqrt{5}}，$

所以 $f(n) = {1 \over \sqrt{5}}[({1 + \sqrt{5} \over 2})^n - ({1 - \sqrt{5} \over 2})^n]$

只要我们把这个公式转换成代码就可以求解了。

class Solution {
public:
    int climbStairs(int n) {
        double sqrt5 = sqrt(5);
        // 主意这里是 n + 1
        double fibn = pow((1 + sqrt5) / 2, n + 1) - pow((1 - sqrt5) / 2, n + 1);
        return (int)round(fibn / sqrt5);
    }
};

爬楼梯升级

条件改为每次你可以爬 $1$ 到 $n$ 个台阶。那么有多少种不同的方法可以爬到楼顶呢？

根据上题目的规律，可以得出下面公式：

$f(n)=f(0)+f(1)+f(2)+…+f(n-2)+f(n-1)$

因为 $f(n-1)=f(0)+f(1)+f(2)+…f(n-2)$

所以 $f(n)=2f(n-1)$

因为 $f(0) = f(1) = 1$

所以 $f(2)=2f(1)=2，f(3)=2f(2)=4，f(4)=2f(3)=8$

所以 $f(n)=2^{n-1}$

其实还有一个更巧妙的思路：一共要上 $n$ 个台阶，每次都可以爬 $1$ 到 $n$ 个台阶，算一共又多少种方法，那么到第 $n$ 个台阶的时候，把前面 $n-1$ 个台阶被踩和不被踩的可能性数量统计出来就是答案了，也就是 $2^{n-1}$ 。

代码过于简单，就不列出来了。