70. Climbing Stairs

Loading...LeetCode

n 只要是大于等于 2 的数，最后一步就只可能是 2 或 1，则走 n 阶的方法只有两大类：

1. 最后走1步的

2. 最后走2步的

也就是说： f(n) = f(n-1) + f(n-2)

即 fibonacci 数列。

fibonacci - A

class Solution:
    def climbStairs(self, n: int) -> int:
        # f(n) = f(n-1) + f(n-2)
        if n <= 2: return n
        f = [0 for _ in range(n+1)]
        f[1], f[2] = 1, 2
        
        for i in range(3, n+1):
            f[i] = f[i-1] + f[i-2]
            
        return f[n]

fibonacci - B

class Solution:
    def climbStairs(self, n):
        a,b = 1,0
        for _ in range(n):
            a,b = a+b,a
        return a