算法题 - 跳楼梯

提问：有一道编程题是跳楼梯类型的：有M级楼梯，若每次只能向上跳1级或4级或7级，那么要走上M级，共有多少种写法，请用C语言写出这到题的最优解法，最好用递归来解决，并给每行代码和代码块添加注释

解答：这是一个动态规划问题，我们可以使用递归和备忘录的方法来解决。首先定义一个数组dp，其中dp[i]表示走上i级楼梯的写法数量。然后从1级开始，依次计算到达每一级的写法数量，最后返回dp[M]即可。

#include <stdio.h>

// 定义一个数组用于存储每个阶段的写法数量
int dp[100];

// 递归函数，计算到达第n级的写法数量
int jump(int n) {
    // 如果已经计算过，直接返回结果
    if (dp[n] != -1) {
        return dp[n];
    }

    // 如果n为0或1，说明已经到达顶部，返回1
    if (n == 0 || n == 1) {
        return 1;
    }

    // 初始化当前阶段的写法数量为0
    int count = 0;

    // 遍历所有可能的跳跃步数，累加到达当前阶段的写法数量
    for (int i = 1; i <= 3; i++) {
        if (n - i >= 0) {
            count += jump(n - i);
        }
    }

    // 将当前阶段的写法数量存入数组，并返回结果
    dp[n] = count;
    return count;
}

int main() {
    int M;
    printf("请输入楼梯级数：");
    scanf("%d", &M);

    // 初始化备忘录数组
    for (int i = 0; i <= M; i++) {
        dp[i] = -1;
    }

    // 调用递归函数，计算到达M级的写法数量
    int result = jump(M);
    printf("共有%d种写法
", result);

    return 0;
}

提问：有一道编程题是跳楼梯类型的：有M级楼梯，若每次只能向上跳1级或4级或7级，那么要走上M级，共有多少种写法，请用C语言写出这到题的最优解法，最好用递归来解决，并给每行代码和代码块添加注释，然后将运行后的效果展示出来给我看，然后再用备忘录的解题方法再给我解一遍并输出代码给我

解答：

递归解法：

#include <stdio.h>
// 递归函数，计算跳上M级楼梯的方法数
int jump(int M, int memo[]) {
    // 如果已经计算过，直接返回结果
    if (memo[M] != -1) {
        return memo[M];
    }
    // 如果楼梯只有一级，只有一种方法
    if (M == 1) {
        return 1;
    }
    // 如果楼梯只有两级或三级，有两种方法
    if (M == 2 || M == 3) {
        return 2;
    }
    // 初始化方法数为0
    int count = 0;
    // 遍历所有可能的跳跃步数
    for (int i = 1; i <= 3; i++) {
        // 如果当前跳跃步数小于等于楼梯剩余级数，递归计算剩余级数的方法数
        if (i <= M) {
            count += jump(M - i, memo);
        }
    }
    // 将结果存入备忘录
    memo[M] = count;
    return count;
}

int main() {
    int M;
    printf("请输入楼梯级数：");
    scanf("%d", &M);
    // 初始化备忘录数组
    int memo[M + 1];
    for (int i = 0; i <= M; i++) {
        memo[i] = -1;
    }
    // 调用递归函数，计算跳上M级楼梯的方法数
    int result = jump(M, memo);
    printf("共有%d种写法", result);
    return 0;
}

备忘录解法：

#include <stdio.h>
// 动态规划解法，计算跳上M级楼梯的方法数
int jump_dp(int M) {
    // 初始化备忘录数组
    int memo[M + 1];
    for (int i = 0; i <= M; i++) {
        memo[i] = -1;
    }
    // 初始化基本情况
    memo[1] = 1;
    memo[2] = 2;
    memo[3] = 4;
    // 动态规划求解
    for (int i = 4; i <= M; i++) {
        int count = 0;
        for (int j = 1; j <= 3; j++) {
            if (j <= i) {
                count += memo[i - j];
            }
        }
        memo[i] = count;
    }
    return memo[M];
}
int main() {
    int M;
    printf("请输入楼梯级数：");
    scanf("%d", &M);
    // 调用动态规划解法，计算跳上M级楼梯的方法数
    int result = jump_dp(M);
    printf("共有%d种写法", result);
    return 0;
}