一、题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
二、算法分析
第n层台阶的跳法为直接跳上第n层的跳法，加上第n-1层台阶的跳法，加上第n-2层台阶的跳法加....上第1层台阶的跳法。
比如，要跳到第3层，方法为直接跳上第3层的跳法，加上跳到第2层的跳法，加上跳到第1层的跳法。f(3)=1+f(2)+f(1)=1+2+1 = 4；
要跳到第4层，方法为直接跳上第4层的跳法，加上跳到第3层的跳法，加上跳到第2层的跳法加上跳到第1层的跳法。f(4)=1+f(3)+f(2)+f(1)=1+4+2+1 = 8；
为什么是这样呢，其实跟普通的跳台阶相比，他就是多了选择罢了，把这些选择都算上就好啦！
此处还是采用记事本法，记录每一个台阶的跳数，避免重复计算，
三、算法实现
public class Solution {
int[] log = new int[1000];
public int JumpFloorII(int target) {
return getF(target);
}
public int getF(int n){
if(n==0||n==1||n==2){
return n;
}
if(log[n]!=0){
return log[n];
}else{
//所有跳法之和
for(int i = 0 ; i < n ; i++){
log[n]+=getF(i);
}
log[n]++;//一次跳n个的情况
}
return log[n];
}
}
文章为个人编辑，如有错误，欢迎指正！
