提问：有一道编程题是跳楼梯类型的：有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;
}
