[已解决]爬楼

lukaka

小明爬楼，每次可以爬一个台阶，或者2个台阶，或者3个台阶，若有n个台阶，会有多少种爬楼的结果。请编写代码解决这个问题

最佳答案

月排行榜 / 总排行榜

FishC

5 天前

思路： 这是一个动态规划问题。定义 dp[i] 为爬到第 i 个台阶的方法数，则初始条件 dp[0]=1（原地不动），dp[1]=1，dp[2]=2。对于 i>=3，递推式为 dp[i]=dp[i-1]+dp[i-2]+dp[i-3]，最终返回 dp[n]。以下为 Python 代码实现：

1. 
   
2. def climb_stairs(n):
   
3.     if n < 0:
   
4.         return 0
   
5.     if n <= 2:
   
6.         return [1, 1, 2][n]
   
7.     dp = [0] * (n + 1)
   
8.     dp[0], dp[1], dp[2] = 1, 1, 2
   
9.     for i in range(3, n + 1):
   
10.         dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
    
11.     return dp[n]
    
12. 
    
13. # 测试
    
14. print(climb_stairs(5))  # 输出 13
    

复制代码

此代码可直接运行，n 为台阶数，返回不同爬楼方法的总数。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

跳转到最佳答案楼层

FishC

思路： 这是一个动态规划问题。定义 dp[i] 为爬到第 i 个台阶的方法数，则初始条件 dp[0]=1（原地不动），dp[1]=1，dp[2]=2。对于 i>=3，递推式为 dp[i]=dp[i-1]+dp[i-2]+dp[i-3]，最终返回 dp[n]。以下为 Python 代码实现：

1. 
   
2. def climb_stairs(n):
   
3.     if n < 0:
   
4.         return 0
   
5.     if n <= 2:
   
6.         return [1, 1, 2][n]
   
7.     dp = [0] * (n + 1)
   
8.     dp[0], dp[1], dp[2] = 1, 1, 2
   
9.     for i in range(3, n + 1):
   
10.         dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
    
11.     return dp[n]
    
12. 
    
13. # 测试
    
14. print(climb_stairs(5))  # 输出 13
    

复制代码

此代码可直接运行，n 为台阶数，返回不同爬楼方法的总数。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

小派

经典爬楼问题，用 DP 很快捷。思路是：dp[i] = dp[i-1] + dp[i-2] + dp[i-3]，因为到达第 i 级台阶的最后一步可以是爬1步、2步或3步。

代码示例：
n = int(input())
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
    if i >= 1: dp[i] += dp[i-1]
    if i >= 2: dp[i] += dp[i-2]
    if i >= 3: dp[i] += dp[i-3]
print(dp[n])

空间可以优化到 O(1)，有兴趣的话试试看～

lukaka

小派 发表于 2026-5-19 20:28
经典爬楼问题，用 DP 很快捷。思路是：dp = dp + dp + dp，因为到达第 i 级台阶的最后一步可以是爬1步、2步 ...

好的，我试试