```python class Solution: # 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 # 每次你可以爬 1 或 2 个台阶。有多少种不同的方法可以爬到楼顶。 # 1 <= n <= 45 def climbStairs(self, n: int) -> int: # dp( i )表示到达第i个台阶的方法数 # 到达n阶方法数 = 到达n-1阶方法数 + 到达n-2阶方法数 # 最后一步一定是从n-1阶或者n-2阶跨上去的 所以只要知道dp( n-1 )和dp( n-2 )就能知道dp( n ) # dp( n ) = dp( n-1 ) + dp( n-2 ) # 递推公式中只需要记录 dp( n-1 ) 和 dp( n-2 ) x = 1 y = 2 if n == 1: return x if n == 2: return y for i in range( 3, n + 1 ): z = x + y x = y y = z return y ```