台階很高,青蛙跳不跳?

青蛙總是被被要求跳台階,我想,他一定很累的!

一隻青蛙一次可以跳上1級台階,也可以跳上2級台階。求該青蛙跳上一個 n 級的台階總共有多少種跳法?

對於這樣的問題,n可大可小,如果n很小,我們可以直觀暴力拆解就可以得到答案,但是如果n很大,那麼這個問題就升級了。

一般處理問題,我們最直接的思路,可能就是分治,將大問題拆解為小問題,分而解決。

在此,也不例外。

首先我們知道青蛙一次能跳一級或者兩級。

假定最後一跳跳一級,則剩餘n-1個台階,則問題化為解決跳上n-1個台階的問題。

假定最後一跳跳兩級,則剩餘n-2個台階,則問題化為解決跳上n-2個台階的問題。

所以歸總起來,總的可能的跳法為(n-1)個台階和(n-2)個台階問題的總和。

我們假定解決方案為f(n),則f(n) = f(n-1) + f(n-2) ,這裡我們假定n是大於2的。

當n = 1 時,青蛙跳一級即可,f(1) = 1。

當n = 2 時,青蛙可以連跳兩個一級或者跳一個兩級,f(2) = 2。

觀察f(n) = f(n-1) + f(n-2) 公式,你們首先想到的是什麼?對的,是遞歸,級聯求解:

 public static long jump(int n) {
        if (n < 3) {
            return n;
        }

        return jump(n - 1) + jump(n - 2);
    }

我們以影像化展示一下這個過程:

圖中以相同顏色標識了遞歸過程中會產生重複計算的節點。

重複是一種算力和資源不必要的浪費,我們可以對此進行優化:

對於上述的遞歸運算,我們可以看到,是由後至前計算的,也即從f(n)->f(1)。也就是我們需要知道向前的每一個位置的方案結果。我們換個方向,從前至後連續計算出每個位置的方案,則最後的位置即為我們所要的結果,同時也可以規避重複計算的問題:

程式碼實現:

public static long jumpx(int n) {
        if (n < 3) {
            return n;
        }

        //每個位置存儲下標(i + 1)個台階的可能結果f(i + 1),所以n個台階即為計算f(n - 1)
        Long[] arr = new Long[n];
        arr[0] = 1L; //一個台階
        arr[1] = 2L; //兩個台階
        //從 n = 3 開始循環計算
        for (int i = 2; i < n; i++) {
            arr[i] = arr[i - 1] + arr[i - 2];
        }
        return arr[n - 1];
    }

我們通過增加一個長度為n的數組空間佔用來換取演算法耗時優化,相對於遞歸演算法,耗時上有數量級差別。

耗時減少了,但是空間似乎浪費了,其實,也沒必要存儲每一個方案的結果,我們只需要知道【前一個】,【前兩個】以及【當前】的幾個變數。

改造如下:

public static long jumpy(int n) {
        if (n < 3) {
            return n;
        }

        //第三節台階方案值f(3) = f(2) + f(1) = 1 + 2 = 3;
        long preTwoCount = 1; //一個台階
        long preOneCount = 2; //兩個台階
        long stepsCount = 0; //n個台階
        //從 n = 3 開始循環計算
        for (int i = 2; i < n; i++) {
            stepsCount = preOneCount + preTwoCount;
            preOneCount = stepsCount;
            preTwoCount = preOneCount;
        }
        return stepsCount;
    }

空間複雜度降為O(1)。