JZ69 跳臺階

描述

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

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

方法1 遞歸

思路

題目分析，假設(shè)f[i]表示在第i個臺階上可能的方法數(shù)。
逆向思維。如果我從第n個臺階進(jì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 遞歸改進(jìn)

思路

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

代碼

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 動態(tài)規(guī)劃

思路

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

具體做法：
  step 1：創(chuàng)建一個長度為n+1的數(shù)組，因?yàn)橹挥衝+1才能有下標(biāo)第n項(xiàng)，我們用它記錄前n項(xiàng)斐波那契數(shù)列。
  step 2：根據(jù)公式，初始化第0項(xiàng)和第1項(xiàng)。
  step 3：遍歷數(shù)組，依照公式某一項(xiàng)等于前兩項(xiàng)之和，將數(shù)組后續(xù)元素補(bǔ)齊，即可得到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));
    }

}

當(dāng)前標(biāo)題：每日算法之跳臺階
文章位置：http://jinyejixie.com/article10/dsdihgo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供關(guān)鍵詞優(yōu)化、品牌網(wǎng)站制作、移動網(wǎng)站建設(shè)、響應(yīng)式網(wǎng)站、品牌網(wǎng)站設(shè)計、App開發(fā)

廣告

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