一、题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

二、算法分析

第n层台阶的跳法为第n-1层台阶的跳法加上第n-2层台阶的跳法。

比如，要跳到第3层，方法为跳到第2层的跳法加上跳到第1层的跳法。f(3)=f(2)+f(1)=2+1 = 3；

为什么是这样呢，不难发现，当我们处于第n层的时候，我们只有可能是从第n-1层或n-2层跳上来得，所以，总跳法数算法应为f(n)=f(n-1)+f(n-2)

此处还是采用记事本法，记录每一个台阶的跳数，避免重复计算，这题也可以用动态规划来做，但是我比较懒，，，，，，

三、算法实现

public class Solution {
    
    int[] log = new int[1000];
    public int JumpFloor(int target) {
        for(int i = 0 ; i < 1000 ; i++){
            log[i] = 0;
        }
        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{
            log[n] = getF(n-1)+getF(n-2);
        }
        return log[n];
    }
}

文章为个人编辑，如有错误，欢迎指正！