变态跳台阶

题目：

一只青蛙一次可以跳上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];
    }
}