猴子爬山一只顽猴在一座有50级台阶的小山上爬山跳跃。上山时需从山脚至山顶往上跳50级台阶，一步可跳1级，或跳2级，或跳3级，求上山有多少种不同的跳法？ （请用递归和递推方法分别实现，并比较两者的运行效率）写代码

这是一个经典的动态规划问题，通常称为“猴子爬楼梯”或“汉诺塔问题”的变体。我们可以使用递归和迭代（即递推）两种方法来解决这个问题。

**递归方法：**
递归的基本思路是从最后一级开始向上倒推，每一级都有三种选择：跳一级、跳两级或者跳三级。当到达第n级时，会有之前n-1级的所有可能性。

def recursive_jumps(n):
    if n <= 1:  # 基本情况：如果只剩1级或0级，只有一种方法（直接跳上去）
        return 1
    else:
        return recursive_jumps(n - 1) + recursive_jumps(n - 2) + recursive_jumps(n - 3)

递归方法虽然直观，但由于重复计算较多，时间复杂度较高，大约是O(7^n)，其中7是所有可行跳跃的最大步数。

**递推方法（动态规划）：**
递推方法通过创建一个数组存储已经计算过的结果，避免了重复计算，提高了效率。

def dynamic_jumps(n, dp = [0] * (n+1)):
    for i in range(1, n+1):
        dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
    return dp[n]

递推方法的时间复杂度是线性的，大约为O(n)，因为只遍历了一次数组。

相关问题

猴子爬山一只顽猴在一座有50级台阶的小山上爬山跳跃。上山时需从山脚至山顶往上跳50级台阶，一步可跳1级，或跳2级，或跳3级，求上山有多少种不同的跳法？ （请用递归和递推方法分别实现，并比较两者的运行效率）

这个问题是一个经典的动态规划问题，可以使用递归和递推两种方法解决。

**递归解法**：
设f(n)表示到达第n级台阶的不同跳法数，递归规则如下：
- 如果n=1，只有1种方法（直接跳一级），f(1)=1；
- 否则，f(n) = f(n-1) + f(n-2) + f(n-3)，因为可以从前一级、前两级或前三级跳到第n级。

递归函数表达式如下：

def recursive_ways(n):
    if n <= 0:
        return 0
    elif n == 1 or n == 2 or n == 3:
        return 1
    else:
        return recursive_ways(n - 1) + recursive_ways(n - 2) + recursive_ways(n - 3)

递归方法虽然直观，但由于重复计算较多，效率较低，时间复杂度大约为O(4^n)。

**递推解法**（也叫记忆化搜索或自底向上策略）：
我们可以创建一个大小为n+1的数组dp[n]，其中dp[i]表示到达第i级台阶的不同跳法数。这种方法避免了重复计算，提高了效率。

def dynamic_programming_ways(n):
    dp = [0] * (n + 1)
    dp[1], dp[2], dp[3] = 1, 1, 1  # 初始化基础情况

    for i in range(4, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

    return dp[n]

递推方法的时间复杂度为O(n)，因为它只需要遍历一次数组。

**运行效率比较**：
递归方法在每次递归调用时都会进行相同的计算，造成大量冗余，而递推方法通过预先存储中间结果，避免了这种重复，因此在处理大规模数据时，递推方法会更快更有效率。对于小规模的问题，两者差距不大；但对于大型问题，递推方法的优势就很明显了。

1.一只顽猴在一座有n级台阶的小山上爬山跳跃。上山时需从山脚至山顶往上跳n级台阶， 一步可跳1级， 或跳2级，或跳3级， 求上山有多少种不同的跳法? (递归思想)

这是一个典型的递归问题。要计算一只顽猴在有n级台阶的山上跳跃的不同方式数量，我们可以基于以下思路：

1. 如果n为0或1，那么只有一种跳法，即直接到达或直接跳到第一级。
2. 如果n为2，有两种跳法：一次跳两级或分两次，每次跳一级。
3. 如果n为3，有四种跳法：一次跳三级，或跳一级后跳两级，或先跳两级再跳一级，或分三次各跳一级。
4. 对于n>3的情况，到达第n级台阶的方式可以由到达第(n-1)级台阶跳一级、到达第(n-2)级台阶跳两级，以及到达第(n-3)级台阶跳三级这三种情况累加得到。

递归式可以表示为：
F(n) = F(n-1) + F(n-2) + F(n-3)

其中，F(n)表示爬到第n级台阶的不同方式数。

以下是递归函数的基本形式（伪代码）：

FUNCTION countWays(n)
    IF n == 0 OR n == 1 THEN
        RETURN 1
    ELSE IF n == 2 THEN
        RETURN 2
    ELSE IF n == 3 THEN
        RETURN 4
    ELSE
        RETURN countWays(n-1) + countWays(n-2) + countWays(n-3)
    END IF
END FUNCTION

注意：这种递归方法的时间复杂度很高，因为它会重复计算很多子问题。在实际应用中，可以使用动态规划（DP）或记忆化递归来优化性能。