LeetCode 70 Climbing Stairs爬楼梯

LeetCode试题链接(英文)
问题描述：
有一座高度是N（N是大于0的整数）级台阶的楼梯，从下往上走，每跨一步只能向上1级或者2级台阶。求出一共有多少种走法。

示例：
若N=3，共有3种走法
走法1：每次走1级台阶，一共走3步。(1步+1步+1步)
走法2：先走1级，再走2级。(1步+2步)
走法3：先走2级，再走1级。(2步+1步)

python3实现代码(表格内容为在leetcode上提交的反馈信息)

方法1.递归求解(自顶向下)

思路: 首先思考只差一步到达第n级台阶时的状态：因为我们一步可选择向上1级或者2级，所以要达到最终的状态前有2个子状态（子状态分别是a.站在第n-1级台阶和b.站在第n-2级台阶上）。由此得到我们算法的核心公式：
f(N) = f(N-1) + f(N-2)，而每一个子状态又可以当作一种最终状态，比如子状态N-1看作最终状态，则有f(N-1) = f(N-1-1) + f(N-1-2)。所以公式可以直接写成一般式f(n) = f(n-1) + f(n-2).

1
2
3
4
5
6

class Solution:
    def climbStairs(self, n: int) -> int:
        if n<=0: return 0
        if n==1: return 1
        if n==2: return 2
        return self.climbStairs(n-1)+self.climbStairs(n-2)

树的高度为N，节点个数近似于2的n次方，所以时间复杂度近似于O(2ⁿ)

方法2.备忘录方法（自顶向下）

如上图所示，我们发现方法1中很多地方被重复计算了（相同颜色代表着重复的部分），如果我们每算出一个颜色的方块的数值就记录下来，这样就减少了很多重复的计算。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    n2step={}
    def climbStairs(self, n: int) -> int:
        if n<=0: return 0
        if n==1: return 1
        if n==2: return 2
        if n in Solution.n2step:
            return Solution.n2step[n]
        else:
            Solution.n2step[n] = self.climbStairs(n-1)+self.climbStairs(n-2)
            return Solution.n2step[n]

此时空间复杂度为O(n),时间复杂度也为O(n)。

方法3.动态规划求解（自底向上）

我们之前两个方法的核心的递归式f(n) = f(n-1) + f(n-2)是一个自顶向下求解的式子。
现在尝试一下自底向上的逻辑： 首先是下图示意的初始状态：
接下来迭代出3层楼梯：
然后是4层楼梯： 由此逐步累加到我们的目标第N层楼梯。 此时的思路是：
要达到状态n前有2个子状态（子状态分别是a.站在第n-1级台阶和b.站在第n-2级台阶上），
当在第n-1级台阶时，走一步1级到达最终状态；当在第n-2级台阶时，有两种方法到第n级台阶（走两步1级和走一步2级）。
完成迭代之后，往前移一层，如图a到图b变化的过程。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def climbStairs(self, n):
        if n == 1:
            return 1
        a, b = 1, 2 #a表示f(n-1),b表示f(n-2)
        for i in range(2, n):
            tmp = b
            b = a+b
            a = tmp
        return b

当前时间复杂度仍为O(n)，但空间复杂度降为O(1)。

一个思考

个人认为自顶向下和自底向上有一个容易混淆的地方，但是我还没有看到有人讨论过这个问题（可能是只有我会混淆吧）
两种方法中都存在两个子状态n-1和n-2。递归求解（自顶向下）的解法是f(n) = f(n-1) + f(n-2)；动态规划（自底向上）的解法有一点像f(n) = f(n-1) + 2*f(n-2)。
乘2是因为站在n-2时，有向上1级和向上2级可以选择，这在动态规划（自底向上）里是很自然的（所以有人说正常的思路应该是一步一步往上走的自底向上的求解方法）。
但是其实在递归求解里，当计算f(n-1)时，会把站在n-2级台阶再向上1级的情况包含进去，所以f(n-2)就不需要乘2了。

递归式是f(n) = f(n-1) + f(n-2)

参考链接

• 动态规划入门（以爬楼梯为例）