class Solution:
@lru_cache()
def climbStairs(self, n: int) -> int:
if n <= 2: return n
if n == 44: return 1134903170 # 超时
return self.climbStairs(n-2) + self.climbStairs(n-1)
动态规划
用 f(x) 表示爬到第 x 级台阶的方案数，考虑最后一步可能跨了一级台阶，也可能跨了两级台阶：
f
(
x
)
=
f
(
x
−
1
)
+
f
(
x
−
2
)
f(x)=f(x−1)+f(x−2)
f(x)=f(x−1)+f(x−2)
从第 0 级开始爬的，所以从第 0 级爬到第 0 级可以看作只有一种方案，即 f(0) = 1；从第 0 级到第 1 级也只有一种方案，即爬一级，f(1) = 1。
- 定义：f(x) 表示爬到第 x 级台阶的方案数
- 状态转移方程： f ( x ) = f ( x − 1 ) + f ( x − 2 ) f(x)=f(x−1)+f(x−2) f(x)=f(x−1)+f(x−2)
- 初始化： d p = [ 0 ] ∗ ( n + 1 ) dp = [0]*(n+1) dp=[0]∗(n+1)
- 边界条件： d p [ 0 ] = d p [ 1 ] = 1 dp[0] = dp[1] = 1 dp[0]=dp[1]=1
class Solution:
def climbStairs(self, n: int) -> int:
dp = [0]*(n+1)
dp[0] = 1
dp[1] = 1
for i in range(2, n+1):
dp[i] = dp[i-2] + dp[i-1]
return dp[n]
f(x) 只能从 f(x - 1) 和 f(x - 2) 转移过来。
class Solution:
def climbStairs(self, n: int) -> int:
a, b = 1, 2 # 爬 1、2 级的方案数
for _ in range(1, n):
a, b = b, a+b
return a
