70. 爬楼梯 (Easy) - 动态规划

class Solution:
    def climbStairs(self, n: int) -> int:
        """
        空间优化的动态规划
        时间: O(n)
        空间: O(1)
        """
        if n <= 2:
            return n

        prev2 = 1  # dp[i-2]
        prev1 = 2  # dp[i-1]

        for i in range(3, n + 1):
            curr = prev1 + prev2
            prev2 = prev1
            prev1 = curr

        return prev1

# 测试
sol = Solution()
print(sol.climbStairs(5))   # 8
print(sol.climbStairs(10))  # 89