只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。java代码实现
时间: 2024-11-09 09:21:56 浏览: 32
这个问题属于动态规划的经典问题,通常被称为“爬楼梯”或“斐波那契数列”的变体。青蛙跳上n级台阶的方案可以通过计算前两个阶段的方案数得到。当青蛙能直接跳到第n级时,它有两种选择:从第n-1级跳或者从第n-2级跳。所以,对于任意n,总的跳法数等于跳n-1级的方案数加上跳n-2级的方案数。
Java代码实现如下:
```java
public class Solution {
public int jump(int n) {
if (n <= 0) return 0;
// 初始化数组,存储每个位置的最大跳跃次数
int[] dp = new int[n + 1];
dp[0] = 1; // 跳0级只有1种方法
dp[1] = 1; // 跳1级也只有1种方法
for (int i = 2; i <= n; ++i) {
// 对于每个位置,如果可以从当前位置直接跳到终点,则将到达终点的方法数加入结果
if (i + 1 <= n) {
dp[i] += dp[i + 1]; // 直接跳一步
}
// 如果可以从当前位置跳两步到达,则也将到达终点的方法数加入结果
if (i + 2 <= n) {
dp[i] += dp[i + 2]; // 跳两步
}
}
return dp[0]; // 返回达到n级的最短路径数
}
}
```
阅读全文