leetcode-0070 爬楼梯

[meishaoming]

https://leetcode-cn.com/problems/climbing-stairs/

审完题后先分析一下：

假设对于 n 阶台阶，有 f(n) 种爬法

对于每一步（还剩下2个以上台阶的话），有两种选择：

1. 跨 1 阶，剩下 f(n-1) 种爬法
2. 跨 2 阶，剩下 f(n-2) 种爬法

f(n) = f(n-1) + f(n-2) ，这是一个 斐波那契 (Fibonacci) 啊。

自顶向下，带备忘

class Solution:
    def climbStairs(self, n: int) -> int:
        memo = {}

        def climb(n):
            if n in memo:
                return memo[n]
            if n == 1:
                ans = 1
            elif n == 2:
                ans =  2
            else:
                ans = climb(n-1) + climb(n-2)
            memo[n] = ans
            return ans

        return climb(n)

自底向上

class Solution:
    def climbStairs(self, n: int) -> int:
        memo = {}
        for i in range(1, n+1):
            if i == 1:
                memo[i] = 1
            elif i == 2:
                memo[i] = 2
            else:
                memo[i] = memo[i-1] + memo[i-2]
        return memo[n]

这里用 memo 存储了每一个计算结果，空间复杂度为 O(n)

实际上只需要存前两个值就行了，空间复杂度为 O(1)

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        elif n == 2:
            return 2
        else:
            first, second = 1, 2
            ans = 0
            for i in range(3, n+1):
                ans = second + first
                first = second
                second = ans
            return ans