猴子爬楼梯路径数求解：递归与动态规划实现技术问询

阿华AIGC实验室

2026-5-21

嘿，我来帮你搞定这两个台阶路径问题，一步步拆解给你看～

问题一：猴子每次跨2级或3级台阶，求到达n级楼梯顶端的不同路径数

这个问题的核心是找到状态转移规律，用动态规划就能轻松解决：

假设dp[n]代表到达第n级台阶的不同路径总数。要登上第n级，最后一步只有两种可能：要么从第n-2级直接跨2级上来，要么从第n-3级直接跨3级上来。所以状态转移方程很清晰：

dp[n] = dp[n-2] + dp[n-3]

接下来得先明确边界条件（这是动态规划的关键，错了后面全白搭）：

n=0（地面，默认已经在起点）：路径数为1（啥也不用走就是一种路径）
n=1：没法通过跨2或3级到达，路径数0
n=2：只能直接跨2级上去，路径数1
n=3：要么直接跨3级，要么从第1级跨2级（但第1级到不了），所以实际只有1种路径，dp[3]=1

举几个例子验证下：

n=4：dp[4] = dp[2]+dp[1] =1+0=1，对应唯一路径2→2
n=5：dp[5] = dp[3]+dp[2] =1+1=2，对应路径2→3、3→2

问题二：猴子每次跳过1/2级台阶（即跨2/3级），用递归+动态规划求路径数

结合你的示例来看，这里的“跳过1级台阶”其实就是跨2级（从k到k+2），“跳过2级台阶”就是跨3级（从k到k+3），和问题一的模型完全一致。下面用两种方法实现：

方法一：递归（带记忆化优化）

直接递归会有大量重复计算（比如算dp[5]时会重复算dp[3]、dp[2]），所以我们用缓存来存已经算过的结果，避免做无用功：

Python代码示例

# 用字典缓存已经计算过的结果
memo = {}

def count_paths_recursive(n):
    # 边界情况处理
    if n == 0:
        return 1
    if n < 0:
        return 0
    # 先查缓存，有就直接返回
    if n in memo:
        return memo[n]
    # 递归计算：最后一步要么是跨2级（对应n-2），要么是跨3级（对应n-3）
    memo[n] = count_paths_recursive(n-2) + count_paths_recursive(n-3)
    return memo[n]

举个例子，调用count_paths_recursive(5)时，会先计算count_paths_recursive(3)和count_paths_recursive(2)，结果分别是1和1，加起来就是2，和你的示例完全匹配。

方法二：动态规划（迭代实现）

迭代的动态规划比递归更高效，不需要调用栈，还能优化空间：

基础版（数组存储状态）

def count_paths_dp(n):
    # 先处理特殊情况
    if n == 0:
        return 1
    if n == 1:
        return 0
    if n == 2:
        return 1
    if n == 3:
        return 1
    # 初始化dp数组，dp[i]对应第i级的路径数
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 0
    dp[2] = 1
    dp[3] = 1
    # 从第4级开始迭代计算
    for i in range(4, n + 1):
        dp[i] = dp[i-2] + dp[i-3]
    return dp[n]

空间优化版（只用3个变量）

因为计算dp[i]只需要dp[i-2]和dp[i-3]，所以不用整个数组，用三个变量滚动更新就行：

def count_paths_dp_optimized(n):
    if n == 0:
        return 1
    if n == 1:
        return 0
    if n == 2:
        return 1
    if n == 3:
        return 1
    # a=dp[i-3], b=dp[i-2], c=dp[i-1]
    a, b, c = 1, 0, 1
    for i in range(3, n + 1):
        current = b + a  # dp[i] = dp[i-2] + dp[i-3]
        a, b, c = b, c, current
    return c

验证下示例：