题目一
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共需要多少种跳法
方法一，用递归思路如果只有一级台阶， 一种跳法如果两级台阶，两种跳法，① 每次跳一级 ② 一次跳两级如果三级台阶，三种跳法 ① 每次跳一级，跳三次 ② 一次跳两级，一次跳一级 ③ 一次跳一级，一次跳两级如果是四级台阶， 5种跳法 ① 每次跳一级，跳4次 ，② 两次跳两级 ③每次跳一级，跳两次，一次跳两级，跳一次④ 一次跳一级，一次跳两级，一次跳一级.....
根据上面的表格可以看出前两项的和加起来等于后一项，类似于斐波那契数列，n阶台阶时的跳法看成n的函数f(n),f(n)=f(n-1)+f(n-2)
public class Test {static int f(int n) {if(n < 2) {return 1;}return f(n-1)+f(n-2);}public static void main(String[] args) {int n=4;int result =f(n);System.out.println(result);}}
递归的方法在输入较大的数如 100 ，程序会非常的慢，时间效率低
方法二 迭代f[3] = f[2] + f[1]f[4] = f[3] + f[2]....每次只需要知道他的 n-1项 和 n - 2 项
public int JumpFloor(int target) {if(target <= 0){return 1;}if(target == 1 || target ==2){return target;}int a1 = 1;int a2 = 2;int temp =0;//定义中间变量for(int i =3; i<= target;i++){temp = a1+a2;a1 = a2;a2 = temp;}return temp;}
题目二
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
示例1
输入
3
返回值
4
思路：
f(n)=f(n-1)+f(n-2)+f(n-3)+...+f(1)f(n-1)=f(n-2)++f(n-3)+...+f(1)两个表达式相减f(n)=2 * f(n-1)且 f(1) = 1f(n) = pow(2, n - 1)
public class Solution {public int JumpFloorII(int target) {return (int)Math.pow(2,target -1); }}
