算法簡述
LeetCode - 70 爬樓梯
假設你正在爬樓梯。需要 n 階你才能到達樓頂。每次你可以爬 1 或 2 個台階。你有多少種不同的方法可以爬到樓頂呢？注意：給定 n 是一個正整數。
解決思路
通常對普通算法問題的解決思路常用的辦法是分拆問題。一個大問題能夠分拆為若幹個小問題，然後對小問題進行遞歸或者局部解決。
n階爬樓梯問題适合用這種思路，但首先需要找到分拆的規律。
從特殊情況推算普遍規律
一眼看上去沒法直接看出普遍規律，那麼可以先用特殊情況先歸納一遍，然後再反推普通規律。
首先取幾個值，
n = {1, 2, 3, 4}
對于簡單的情況可以直接計算出結果，設 k 為需要的步數，steps 是實際爬樓梯的方案集合
n = 1, k = 1, steps = {1} n = 2, k = 2, steps = { {1, 1}, {2}} n = 3, k = 3, steps = { {1, 1, 1}, {2, 1,}, {1, 2}} n = 4, k = 5, steps = { {1, 1, 1, 1}, {2, 1, 1}, {1, 2, 1}, {1, 1, 2}, {2, 2}}
接下來分析特殊情況的4個例子可以找到簡單的規律
k[4] = k[3] + k[2] = 3 + 2 = 5
那麼從這裡是否可以推斷得到下面的普遍規律呢？
k[n] = k[n - 1] + k[n -2]
我們需要一個嚴謹的推斷過程。這裡可以考慮動态規劃的思路，首先分拆問題，當階數為i時，設定k = x
- n = i, k = x
- n = i + 1, k = y 首先必然可以得到的其中一個i + 1階的方案是在原先i階的方案上再走1步得到。反過來說，當n= i + 1時，對于所有最後一步是1步的方案，steps 和 n = i 時是相等的。
那麼最後一步是2步的方案是怎樣的呢？也是同樣的思路可以得到， n = i + 1時，最後一步是2步的所有方案，steps 和 n = i - 1時是相等的，而且絕對不會和n = i時重疊。是以可以得到結論是 3 n = i + 2, k = x + y
也就是說，
steps[n] = steps[n -1] + steps[n - 2]
算法實作
基于上面的推論，這個算法可以用兩個思路實作。一個是從下往上計算n = i時的方案數， 另一個是從上往下用遞歸計算n = i時的方案數。
方案一
最簡單的思路是用數組實作，定義數組 steps[n]，n = i，然後從0開始到 i - 1逐個計算方案數。很容易看出這個方案的缺點是記憶體空間占據太多，當n很大的時候配置設定的空間會很浪費。
注意觀察上面的推論，實際上我們隻需要用兩個int即可以記錄步數的變化，
steps[n] = steps[n -1] + steps[n - 2]
比如定義steps[2]，用[0]記錄 n - 1 的方案數，[1] 記錄n - 2的方案數，然後不斷相加并且交換兩個數的位置，這樣也可以得到 n = i 時的方案數。下面是具體代碼實作
public static int ways(int steps) {
int[] ways = new int[2];
ways[0] = 1;
ways[1] = 2;
int k = 1;
while(k < steps) {
ways[(k-1) % 2] += ways[k % 2];
k++;
}
return ways[(k - 1) % 2];
}
複制
方案二
遞歸的思路非常簡單，隻要把我們的推論翻譯進去就行，代碼
public static int waysRecursive(int n) {
if (n > 2) {
return waysRecursive(n - 1) + waysRecursive(n - 2);
} else {
if (n == 2) {
return 2;
} else if (n == 1) {
return 1;
}
}
return 1;
}
複制
算法評估
這兩個算法都可以正确計算出結果，但是在時間開銷上差異很大。方案二在n大于43之後就會運算超過2秒，而方案一在同樣的n值下隻需要1ms就可以得到結果。
因為方案二的遞歸實際上是個指數爆炸的算法，算法複雜度是 O(n²)， 也就是每一個n的方案都會被重複計算接近于無數次。
是以對于這個問題的最優解是方案一。
但在LeetCode上方案一并沒有取得最好的結果， 記憶體和算法時間開銷都隻在中位數，應該還可以再優化到更好的水準。