剑指offer--跳台阶（斐波那契）

谁借莪１个温暖的怀抱￠ 2023-02-14 10:51 61阅读 0赞

## 题目描述 ##

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

## 解决方法 ##

题目理解：青蛙跳上每一个台阶有几种跳法

> **牛客大佬的思路**： 如果青蛙当前在第n级台阶上，那它上一步是在哪里呢？ 由于它可以跳1级台阶或者2级台阶，所以它上一步必定在第n-1,或者第n-2级台阶，也就是说它跳上n级台阶的跳法数是跳上n-1和跳上n-2级台阶的跳法数之和。

跳上第n个台阶的方法有 `f(n)=f(n-1)+f(n-2)`和`斐波那契额数列`的递推式类似

## 递归解法(不推荐) ##

面试不推荐，时间复杂度O(2的n次方)

public class Solution {
        
        public int JumpFloor(int target) {
        
            if(target <= 2){
        
                return target;
            }
            return JumpFloor(target-1)+JumpFloor(target-2);
        }
    }

## 自底向上型循环求解 ##

面试推荐，时间复杂度O(n)

//leetcode
    class Solution {
        
        public int numWays(int n) {
        
            if(n<0){
        
                return 0;
            }
            if(n==0 || n==1){
        
                return 1;
            }
            if(n==2){
        
                return 2;
            }
            int a=1,b=2,temp=0;
            for(int i=3;i<=n;i++){
        
                temp=(a+b)%1000000007;
                a=b;
                b=temp;
            }
            return temp;
    
        }
    }

public class Solution {
        
        public int JumpFloor(int target) {
        
            int a=1,b=1; //注意此处a和b都是1
            for(int i=1;i<target;i++){
        
                b=a+b;
                a=b-a;
            }
            return b;
        }
    }