用c++实现一个顽猴在一座有30级台阶的小山上爬山跳跃。猴子上山一步可跳1级，或跳3级。试求上山的30级台阶有多少种不同的爬法。

这是一个经典的动态规划问题，通常被称为“斐波那契兔子”或“阶梯问题”。我们可以用一个二维数组 `dp` 来记录每一步的不同爬法，其中 `dp[i]` 表示到达第 `i` 阶台阶的所有可能路径数。对于每一步，猴子有两种选择：要么跳一级，要么跳三级。因此，我们通过更新 `dp[i]` 的值来累加之前两步的情况。

以下是简单的 C++ 实现：

#include <iostream>
using namespace std;

int climbStairs(int n) {
    if (n <= 2) {
        return n;
    }
    int dp[n + 1];  // 初始化数组，假设0阶台阶只有一个方案（即不爬）
    dp[1] = 1;
    dp[2] = 2;     // 第二阶台阶有两种方案：一步一阶或一步三阶

    for (int i = 3; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];  // 每一步都可能是前一步或前两步的组合
    }

    return dp[n];
}

int main() {
    int steps = 30;
    cout << "爬上 " << steps << " 级台阶的不同爬法共有 " << climbStairs(steps) << " 种。\n";
    return 0;
}

当调用 `climbStairs(30)`，程序将返回30阶台阶的总爬法数量。

相关问题

一个顽猴在一座有30级台阶的小山上爬山跳跃。猴子上山一步可跳1级，或跳3级。 试求上山的30级台阶有多少种不同的爬法。用递推和递归分别编码实现？用java

这是一个经典的组合数学问题，可以用动态规划（Dynamic Programming）中的“阶乘排列”（rising factorial）或“三角数”（triangular number）的概念来解决。对于每一步，猴子可以选择上一级或者三级，所以总的爬法数可以通过前一步的爬法数相加得到，初始状态时，只有一步，只有一种方式（一步一级或一步三级）。

以下是递推和递归的Java实现：

**递推实现**（动态规划）：

public class MonkeyJumps {
    public static int climbStairs(int n) {
        if (n <= 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        } else {
            return climbStairs(n - 1) + climbStairs(n - 3); // 上一步1级或3级
        }
    }

    public static void main(String[] args) {
        int steps = 30;
        int ways = climbStairs(steps);
        System.out.println("The monkey has " + ways + " different ways to climb the stairs.");
    }
}

**递归实现**（虽然理论上可行，但会非常慢，因为有大量的重复计算）：

public class RecursiveMonkeyJumps {
    public static int recursiveClimbStairs(int n) {
        if (n <= 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        } else {
            return recursiveClimbStairs(n - 1) + recursiveClimbStairs(n - 3); // 递归调用
        }
    }

    //...其他代码同上...
}

递推版本更高效，因为避免了重复计算，而递归版本时间复杂度较高，不适合大型输入。

猴子爬山一只顽猴在一座有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)，因为它只需要遍历一次数组。

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