当前位置 博文首页 > Inmaturity_7的博客：算法练习帖--19--青蛙跳台阶问题(Java)
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。(类似斐波那契数列)
注意：答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
（题目来源：力扣（LeetCode））
0 <= n <= 100
示例 1：
输入：n = 2
输出：2
示例 2：
输入：n = 7
输出：21
示例 3：
输入：n = 0
输出：1
n=1，解法1种
n=2，解法2种
n=3，解法3种
n=4，解法5种
n=5，解法8种
n=6，解法13种
n=7，解法21种
设第n种时我们假设是f(n)
由推断得f(n)=f(n-1)+(n-2)(根据规律或者根据最后一个数的情况向前推演)
特殊:n=1和n=2时,直接可以数出为1种和2种
1. 动态规划
public int numWays(int n) {
if(n<0){
return 0;
}
if(n==0||n==1){
return 1;
}
if(n==2){
return 2;
}
//记录前两个数的跳法,这两数跳法相加等于当前数的跳法
int first=1,second=2;
int third=0;
//动态规划，从3开始一直遍历到n
for(int i=3;i<=n;i++){
//第三个数等于前两个数相加
//这里要注意防止第三个数溢出int最大值
third=(first+second)%1000000007;
//将第二个数赋值给第一个数
first=second;
//将第三个数赋值给第二个数
second=third;
}
return third;
}
2. 递归+记忆优化
注意：直接递归数会造成反复计算同一个值，不可取，用map存储已经计算完的，如果已经计算完，就没必要继续计算了
//存储结果的map
public Map<Integer,Integer> map=new HashMap<Integer,Integer>();
public int numWays(int n) {
if(n<0){
return 0;
}
if(n==0||n==1){
return 1;
}
if(n==2){
return 2;
}
//判断map中是否已经计算过n个台阶的解法
//未解决-->等于上两个值相加，并存储(注意取模)
if(!map.containsKey(n)){
map.put(n, (numWays(n-1)+numWays(n-2))%1000000007);
}
return map.get(n);
}
