台階很高,青蛙跳不跳?
青蛙總是被被要求跳台階,我想,他一定很累的!
一隻青蛙一次可以跳上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)。