JZ69 跳臺階

描述

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

數據范圍：1 \leq n \leq 401≤n≤40
要求：時間復雜度：O(n)O(n) ，空間復雜度： O(1)O(1)

方法1 遞歸

思路

題目分析，假設f[i]表示在第i個臺階上可能的方法數。
逆向思維。如果我從第n個臺階進行下臺階，下一步有2中可能，一種走到第n-1個臺階，一種是走到第n-2個臺階。
所以f[n] = f[n-1] + f[n-2]，那么初始條件了，f[0] = f[1] = 1。 
所以就變成了：f[n] = f[n-1] + f[n-2], 初始值f[0]=1, f[1]=1

代碼

if(target == 0 || target == 1) return 1;
        return jumpFloor(target - 1) + jumpFloor(target - 2);

方法2 遞歸改進

思路

f(2)計算了兩次，f(1)計算了3次，f(0)計算了2次?？梢圆捎靡粋€數組存儲已經被計算過的值
此方法編譯不通過，空間復雜度過高

代碼

int[] f = new int[50];
        if (target <= 1) return 1;
        if (f[target] != 0) return f[target];
        return f[target] = (jumpFloor(target - 1) + jumpFloor(target - 2));

方法3 動態規劃

思路

思路：既然與斐波那契數列相同，我們就把它放入數組中來解決。

具體做法：
  step 1：創建一個長度為n+1的數組，因為只有n+1才能有下標第n項，我們用它記錄前n項斐波那契數列。
  step 2：根據公式，初始化第0項和第1項。
  step 3：遍歷數組，依照公式某一項等于前兩項之和，將數組后續元素補齊，即可得到fib[n]fib[n]fib[n]

代碼

package esay.JZ69跳臺階;

public class Solution {
    public static int jumpFloor(int target) {
        //方法1
        /*if(target == 0 || target == 1) return 1;
        return jumpFloor(target - 1) + jumpFloor(target - 2);*/

        //方法2
        /*int[] f = new int[50];
        if (target <= 1) return 1;
        if (f[target] != 0) return f[target];
        return f[target] = (jumpFloor(target - 1) + jumpFloor(target - 2));*/

        //方法3
        if (target <= 1)
            return 1;
        int[] temp = new int[target + 1];
        //初始化
        temp[0] = 1;
        temp[1] = 1;
        //遍歷相加
        for (int i = 2; i <= target; i++)
            temp[i] = temp[i - 1] + temp[i - 2];
        return temp[target];

    }

    public static void main(String[] args) {
        System.out.println(jumpFloor(37));
    }

}

當前標題：每日算法之跳臺階
文章位置：http://vcdvsql.cn/article10/dsdihgo.html

成都網站建設公司_創新互聯，為您提供關鍵詞優化、品牌網站制作、移動網站建設、響應式網站、品牌網站設計、App開發

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯