考察点:DP 入门——把问题拆成『最后一步』得到递推式,并理解自顶向下(记忆化)与自底向上两种写法及空间优化。
思路:到第 n 阶的走法 = 到第 n-1 阶(再走 1 步)+ 到第 n-2 阶(再走 2 步),即经典斐波那契。
要点(状态定义与转移):
dp[i] = 到达第 i 阶的方法数,则 dp[i] = dp[i-1] + dp[i-2],边界 dp[1]=1, dp[2]=2。# 滚动变量优化空间
def climb(n):
a, b = 1, 2
for _ in range(3, n + 1):
a, b = b, a + b
return b if n >= 2 else a
要点(复杂度与注意):
dp[0] 设错——递推从 1、2 起步;也可用记忆化递归 dfs(n)=dfs(n-1)+dfs(n-2)(带 memo)。题目与答案就在本页;收藏、批注和错题重练在应用内