本文主要是介绍青蛙跳问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
青蛙跳
一：青蛙一次只能跳一级 或者跳两级 n级台阶有多少种方法
动态规划/斐波那契数列 f(n)=f(n-1)+f(n-2) 注意初始化数组的时候不要越界
二：青蛙一次可以跳1级，2级，…………，n级 n级台阶有多少种方法
运行时间：39ms 占用内存：654k
刚开始想成了这样：
从0到n 有一种
从0-1有f(1)种 从1-n有f(n-1)种
从0-2有f(2)种 从2-n有f(n-2)种
………………
这样显然有个问题，重复：从0-2的f(2)种方法已经包含了从0到1的一种方案
正确的应该是这样：
n级的时候可以选择第一次跳1级2………………n级
如果第一步跳1级那么剩下的n-1级有f(n-1)种方案
如果第一步跳2级那么剩下的n-2级有f(n-2)种方案
……………………
也可以返回来理解：n级可以从第1级直接跳过来也可以从第2级直接跳过来 也可以从第0或者n-1直接跳过来 和第一个题目是一样的
也就是最后一步有n中跳法分别是跳n级，n-1级，n-2级………………1级
这样分别对应f(0)+f(1)+………………+f(n-1)--------f(n)=2*f(n-1)
public class Solution {public int JumpFloorII(int target) {if(target==0)return 0;if(target==1) return 1;if(target==2) return 2;int count[]=new int[target+1];count[0]=1;count[1]=1;count[2]=2;for(int i=3;i<=target;i++){count[i]=count[i-1]*2;}return count[target];}
}
添加笔记
这篇关于青蛙跳问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
