从前有一只青蛙想跳台阶去等峰,若该青蛙一次可以跳上1级台阶、也可以跳上2级、还可以跳3级。那么改青蛙从第0级台阶出发,在跳上第n级台阶且在第m级台阶停留过时有多少种跳法。C语言代码
时间: 2024-12-18 10:36:16 浏览: 17
这个问题是一个经典的动态规划问题,通常称为“爬楼梯”或“跳跃阶梯”的变体。我们可以使用一个二维数组 `dp` 来存储从第0级到第n级的不同跳法数,其中 `dp[i]` 表示到达第i级台阶的方式。这里我们假设 m >= i。
以下是使用C语言解决这个问题的一个思路:
```c
#include <stdio.h>
int climbStairs(int n, int m) {
if (n == 0 || m == 0) {
return 1; // 如果台阶数为0,只有一种方式就是不跳
}
int dp[n + 1]; // 初始化数组
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; ++i) {
// 跳1步、2步或3步到达i级
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
}
return dp[n];
}
int main() {
int n = 5, m = 4; // 指定台阶总数和停留台阶位置
printf("青蛙有 %d 种跳法到达第%d级台阶并停留在第%d级.\n", climbStairs(n, m), n, m);
return 0;
}
```
在这个代码里,`climbStairs` 函数计算了到达第n级台阶的所有方法。当`n`等于0或`m`等于0时,只有一种方式,即不跳。然后通过循环更新`dp`数组,直到计算出所有级别的可能性。
阅读全文