爬楼梯：经典动态规划+递归法

爬楼梯

目录

• 摘要
• 解决方案
  • 方法 1：暴力法
  • 方法 2：记忆化递归
  • 方法 3：动态规划
  • 方法 4: 斐波那契数
  • 方法 5: Binets 方法
  • 方法 6: 斐波那契公式

摘要

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

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

解决方案

---

方法 1：暴力法

算法

在暴力法中，我们将会把所有可能爬的阶数进行组合，也就是 1 和 2 。而在每一步中我们都会继续调用 $climbStairs$这个函数模拟爬 1 阶和 2 阶的情形，并返回两个函数的返回值之和。

$$climbStairs(i,n) = climbStairs(i + 1, n) + climbStairs(i + 2, n)$$

其中 $i$ 定义了当前阶数，而 $n$ 定义了目标阶数。

class Solution {
public:
    int climbStairs(int n) {
        return climb_Stairs(0,n);
    }
    int climb_Stairs(int i ,int n){
        if(i > n)return 0;
        if(i == n)return 1;
        return climb_Stairs(i+1,n) + climb_Stairs(i+2,n);
    }
};

复杂度分析

• 时间复杂度：$O(2^n)$。树形递归的大小为 $2^n$ 。

  在 $n=5$ 时的递归树将是这样的：

空间复杂度：$O(n)$。递归树的深度可以达到 $n$ 。

方法 2：记忆化递归

算法

在上一种方法中，我们计算每一步的结果时出现了冗余。另一种思路是，我们可以把每一步的结果存储在 $memo$ 数组之中，每当函数再次被调用，我们就直接从 $memo$数组返回结果。

在 $memo$ 数组的帮助下，我们得到了一个修复的递归树，其大小减少到 $n$ 。

class Solution {
public:
    int climbStairs(int n) {
        int memo[n+1];
        return climb_Stairs(0,n,meno);
    }
    int climb_Stairs(int i ,int n,int meno[]){
        if(i > n)return 0;
        if(i == n)return 1;
        if(meno[i] > 0)return meno[i];
        meno = climb_Stairs(i+1,n,meno) + climb_Stairs(i+2,n,meno);
        return meno[i];
    }
};

复杂度分析

• 时间复杂度：$O(n)$。树形递归的大小可以达到 $n$。
• 空间复杂度：$O(n)$ 。递归树的深度可以达到 $n$ 。

方法 3：动态规划

算法

不难发现，这个问题可以被分解为一些包含最优子结构的子问题，即它的最优解可以从其子问题的最优解来有效地构建，我们可以使用动态规划来解决这一问题。

第 ii 阶可以由以下两种方法得到：

1. 在第$ (i-1)$阶后向上爬一阶。
2. 在第 $(i-2)$阶后向上爬 $2 $阶。

所以到达第 ii 阶的方法总数就是到第$ (i-1)$ 阶和第 $(i-2)$阶的方法数之和。

令$ dp[i]$ 表示能到达第 $i$阶的方法总数：

$$dp[i]=dp[i-1]+dp[i-2]$$

代码：

class Solution {
public:
    int climbStairs(int n) {
        if(n <= 3)return n;
        int dp[n+1];
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3;i <= n; ++i)
            dp[i] = dp[i-1] + dp[i-2];
        return dp[n];
    }
};

复杂度分析

• 时间复杂度：$O(n)$，单循环到$n$ 。
• 空间复杂度：$O(n)$。$dp$数组用了 $n$ 的空间。

方法 4: 斐波那契数

算法

在上述方法中，我们使用 $dp$ 数组，其中 $dp[i]=dp[i-1]+dp[i-2]$。可以很容易通过分析得出 $dp[i]$ 其实就是第$ i$个斐波那契数。

$$Fib(n)=Fib(n-1)+Fib(n-2)$$

现在我们必须找出以 $1$ 和 $2$ 作为第一项和第二项的斐波那契数列中的第 $n$ 个数，也就是说 $Fib(1)=1$ 且 $Fib(2)=2$。

class Solution {
public:
    int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        int first = 1;
        int second = 2;
        for (int i = 3; i <= n; i++) {
            int third = first + second;
            first = second;
            second = third;
        }
        return second;
    }
};

复杂度分析

• 时间复杂度：$O(n)$。单循环到 $n$，需要计算第 $n$ 个斐波那契数。
• 空间复杂度：$O(1)$。使用常量级空间。

方法 5: Binets 方法

算法

这里有一种有趣的解法，它使用矩阵乘法来得到第 nn 个斐波那契数。矩阵形式如下：

我们需要为我们的问题做的唯一改动就是将斐波那契数列的初始项修改为 2 和 1 来代替原来的 1 和 0 。或者，另一种方法是使用相同的初始矩阵 $Q$并使用 $result = Q^{n}[0,0]$ 得出最后结果。发生这种情况的原因是我们必须使用原斐波那契数列的第 2 项和第 3 项作为初始项。

public class Solution {
    public int climbStairs(int n) {
        int[][] q = {{1, 1}, {1, 0}};
        int[][] res = pow(q, n);
        return res[0][0];
    }
    public int[][] pow(int[][] a, int n) {
        int[][] ret = {{1, 0}, {0, 1}};
        while (n > 0) {
            if ((n & 1) == 1) {
                ret = multiply(ret, a);
            }
            n >>= 1;
            a = multiply(a, a);
        }
        return ret;
    }
    public int[][] multiply(int[][] a, int[][] b) {
        int[][] c = new int[2][2];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
            }
        }
        return c;
    }
}

复杂度分析

• 时间复杂度：$O(log(n))$。遍历$ log(n)$ 位。
• 空间复杂度：$O(1)$。使用常量级空间。

这里的时间复杂度证明比较复杂，这里就不讨论了

方法 6: 斐波那契公式

算法

我们可以使用这一公式来找出第 $n$ 个斐波那契数：

$$F_n = 1/\sqrt{5}\left[ \left(\frac{1+\sqrt{5}}{2}\right)^{n} - \left(\frac{1-\sqrt{5}}{2}\right)^{n} \right]$$

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