https://leetcode.cn/problems/climbing-stairs/ (opens new window) 需要注意的点

1. 关键是找对关系，f(n) = f(n-1) + f(n-2)， f(1) = 1,f(2) = 2
2. 提供两种类似解法，使用数组和不使用数组

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

        a = 1
        b = 2
        for i in range(2, n):
            a,b = b, a+b
        
        return b

class Solution:
    def climbStairs(self, n: int) -> int:

        # f(1) = 1
        # f(2) = 2

        # f(3) = 1 + 2 = f(1) + f(2)
        # f(4) = f(2) + f(3)
        # 到3层跨一步，到2层跨两步

        stairs = [1,2]
        for i in range(2, n):
            stairs.append(stairs[-1] + stairs[-2])
        
        return stairs[n-1]

done动态规划