題目：
一只青蛙一次可以跳上1級(jí)臺(tái)階宽档，也可以跳上2級(jí)……它也可以跳上n級(jí)。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法。
解析：
首先看一下基本情況:
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(xiàn)(4)=1+F(3)+F(2)+F(1)，其中1代表從下面直接一次跳4個(gè)臺(tái)階的這種可能性俺榆，F(xiàn)(3)代表從初始到第三個(gè)臺(tái)階的所有可能性感昼，在這種情況下可以一步從3階上到4階；同理罐脊，也可以一步從2階到4階定嗓，一步從1階到4階。
故而萍桌，可以推理出宵溅，F(xiàn)(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];
}
}
這道題，關(guān)鍵就是把遞歸的公式找出來(lái)就好上炎，不存在多少難度恃逻。
下面對(duì)于代碼的簡(jiǎn)潔度上進(jìn)行了優(yōu)化：
import java.util.*;
public class Solution {
public int JumpFloorII(int target) {
int[] dp = new int[target+1];
Arrays.fill(dp,1); //把數(shù)組所有的初始值設(shè)為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];
}
}
