跳台阶以及变态跳台阶问题

跳台阶问题：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

解法一：target表示距离目标还有多远，进行递归

public class Solution {    public int JumpFloor(int target) {                    if(target==0){              return 0;          }else if(target==1){              return 1;          }else if(target==2){        	  return 2;          }else{              return JumpFloor(target-2)+JumpFloor(target-1);          }    }    public static void main(String [] args){    	Solution s = new Solution();    	System.out.PRintln(s.JumpFloor(4));     }}解法二：利用斐波那契数列
public class Solution {    public int JumpFloor(int target) {          if(target==1||target==2){        	  return target;          }else{        	  int pre=1;        	  int cur=1;        	  for(int i=0;i<target-1;i++){        		  int temp;        		  temp=cur;        		  cur=pre+cur;        		  pre=temp;        	  }        	  return cur;//如果i<target的话，就return pre;          }    }    public static void main(String [] args){    	Solution s = new Solution();    	System.out.println(s.JumpFloor(4));     }} 
变态跳台阶问题：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
public class Solution {	public int JumpFloorII(int target) {		if(target==0){            return 0;        }else if(target==1){            return 1;        }else if(target==2){      	  return 2;        }else{            return 2*JumpFloorII(target-1);        }  }    public static void main(String [] args){    	Solution s = new Solution();    	System.out.println(s.JumpFloorII(4));     }}解析：
f(0)=0;f(1)=1;f(2)=f(2-1)+f(2-2);//当还剩下两阶时，紧接着还可以在跳一阶，两阶f(3)=f(3-1)+f(3-2)+f(3-3);//当还剩下三阶时，紧接着还可以在跳一阶，两阶，三阶........f(n-1)=f(n-2)+f(n-3)+f(n-4)+...+f(n-1-(n-2))+f(n-1-(n-1));//当还剩下n-1阶时，紧接着还可以在跳一阶，两阶，三阶，...，n-2阶，n-1阶f(n)=f(n-1)+f(n-2)+f(n-3)+f(n-4+...+f(n-(n-1))+f(n-n);可见，f(n)=f(n-1)+f(n-1);