题目：
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
解析：
首先看一下基本情况:
F(0)一定是0，
F(1)=1，
F(2)=2，
F(3)=4, （1+1+1；1+2；2+1；3）
F(4)=8, （1+1+1+1；1+1+2；1+2+1；2+1+1；1+3；3+1；2+2；4）
...
我们可以看出，F(4)=1+F(3)+F(2)+F(1)，其中1代表从下面直接一次跳4个台阶的这种可能性，F(3)代表从初始到第三个台阶的所有可能性，在这种情况下可以一步从3阶上到4阶；同理，也可以一步从2阶到4阶，一步从1阶到4阶。
故而，可以推理出，F(n) = F(N-1)+F(N-2)+F(N-3)+...+F(2)+F(1)+1;
代码：
public class Solution {
public int JumpFloorII(int target) {
if(target <0 ) return 0;
if(target <=2) return target;
int[] dp = new int[target+1];
dp[0]=0;
dp[1]=1;
dp[2]=2;
for(int i=3;i<=target;i++){
dp[i]=1;
for(int j=i-1;j>0;j--){
dp[i]+=dp[j];
}
}
return dp[target];
}
}
这道题，关键就是把递归的公式找出来就好，不存在多少难度。
下面对于代码的简洁度上进行了优化：
import java.util.*;
public class Solution {
public int JumpFloorII(int target) {
int[] dp = new int[target+1];
Arrays.fill(dp,1); //把数组所有的初始值设为1
dp[0]=0; //除了dp[0]
for(int i=2;i<=target;i++){
for(int j=i-1;j>0;j--){
dp[i]+=dp[j];
}
}
return dp[target];
}
}
