遞歸-跳台階-JZ8

描述

一隻青蛙一次可以跳上1級台階，也可以跳上2級。求該青蛙跳上一個n級的台階總共有多少種跳法（先後次序不同算不同的結果）。

示例1

輸入： 2

傳回值： 2

示例2

輸入： 7

傳回值： 21

思路1:

斐波那契數列,遞歸，數組dp 儲存已經求過的值，減少重複計算

時間複雜度：O（n）， 沒有重複的計算

空間複雜度：O（n）和遞歸棧的空間

代碼1

public class Solution {
    public int jumpFloor(int target) {
        int [] dp = new int[target + 1];
        return fib(target, dp);
    }
    private int fib(int target, int [] dp) {
        if(target <= 1) {
            return 1;
        }
        if(target == 2) {
            return 2;
        }
        if(dp[target] != 0) {
            return dp[target];
        }
        int res = jumpFloor(target-1) + jumpFloor(target-2);
        dp[target] = res;
        return res;
    }
}
           

思路2:

斐波那契數列,自底向上,動态規劃壓縮

時間複雜度：O（n）

空間複雜度：O（1）

代碼2

public class Solution {
    public int jumpFloor(int target) {
        if(target == 0) {
            return 0;
        }
        if(target == 1) {
            return 1;
        }
        if(target == 2) {
            return 2;
        }
        int fibMinOne = 2;
        int fibMinTwo = 1;
        int res = 0;
        for(int i = 3; i <= target; i++){
            res = fibMinOne + fibMinTwo;
            fibMinTwo = fibMinOne;
            fibMinOne = res;
        }
        return res;
    }
}