跳台阶-----牛客网面试题

题目描述

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

分析

当每次只跳一级台阶时，只有一种情况

当每次只跳两级台阶时，也是只有一种情况

当又跳一级台阶又跳两级台阶时，我们可以假设第一步跳一级台阶，那么后面的所有的跳法为f(n-1)。当第一步跳两级台阶时，后面所有的跳法为f(n-2)。所有的跳法即是f(n-1)+f(n-2)

归纳

             | 1, (n=1)

f(n) =     | 2, (n=2)

              | f(n-1)+f(n-2) ,(n>2,n为整数)

即一个Fibonacci序列

实现代码如下

public int JumpFloor(int target) {
        if(target <= 0) return -1;
        if(target == 1) return 1;
        if(target == 2) return 2;
        
        int fn1 = 1;
        int fn2 = 2;
        while(target-->2){
            fn2 += fn1;
            fn1 = fn2 - fn1;
        }
        return fn2;
    }