接觸DP最早的應(yīng)該就是這道題了吧泪电，翻了翻leetcode submission發(fā)現(xiàn)最早的是在一年前... 而且是最基礎(chǔ)的DP解法。在膜拜了大神們用矩陣甚至直接上斐波那契數(shù)列公式解法后覺得腦容量有點(diǎn)不太夠用。睬澡。曙砂。嗯，需要寫點(diǎn)東西捋一捋狐蜕，所以這是一個(gè)學(xué)渣（p.s. 話癆）關(guān)于爬樓梯類型題目的總結(jié)（如果有不對的地方歡迎米娜桑批評指正(￣.￣)）宠纯。
題目：Climbing Stairs
You are climbing a stair case. It takes n steps to reach to the top.Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Input：
Argument：達(dá)到最高層的步數(shù)（Integer）
Condition： 每次只能爬一步或者兩步
Output:
達(dá)到最高層可以用多少種不同的方法(Integer)
1. 暴力遞歸
Intuitive:
想法很簡單，既然下一步只有兩種選擇：1步和2步层释， 那么下步走的方法也就是2種婆瓜。總的方法數(shù)即走一步的方法 + 走兩步的方法湃累。
Edge cases:
當(dāng)前走的步數(shù)等于或者大于0時(shí)結(jié)束遞歸
Recursion Tree
例如目標(biāo)層數(shù)是5勃救，那么recursion tree應(yīng)該是這個(gè)樣子滴
可以看到每個(gè)節(jié)點(diǎn)我們都有兩個(gè)選擇碍讨，走一步或者兩步。那么一共有 2^n 個(gè)節(jié)點(diǎn)蒙秒，時(shí)間復(fù)雜度 2^n. 至于空間復(fù)雜度則是樹的深度勃黍，最壞的情況，我們每次只走一步晕讲，深度達(dá)到n覆获。另外也不難看出在遞歸的過程中存在很多重復(fù)的計(jì)算，這就是下一個(gè)算法優(yōu)化的點(diǎn)啦瓢省。
Code：
TC:O(2^n) SC:O(n)
public int climbStairs(int target){
return helper(0, target);
}
public int helper(int step, int target){
//edge cases
if(step == target){
return 1;
}
if(step > target){
return 0;
}
return helper(step + 1, target) + helper(step + 2, target);
}
2. 記憶化搜索
Intuitive:
所以弄息，怎么避免重復(fù)計(jì)算呢？很明顯的想法就是把算過的存起來嘛勤婚，下次計(jì)算前先查一下摹量，有結(jié)果就跳過，沒結(jié)果就算馒胆。就是這樣一個(gè)小小的優(yōu)化缨称， 就把復(fù)雜度從2^n縮減到n(p.s. array 查詢的復(fù)雜度是O(1)),你敢信！嗯祝迂，所以在面試官followup的時(shí)候睦尽，別老想有多fancy或者tricky的變化，逮著最明顯的那個(gè)劣勢優(yōu)化就好~
Edge cases:
Edge case 是跟暴力遞歸的一樣的型雳。
Code:
TC: O(n) SC: O(n)
public int climbStairs(int target){
int[] memo = new int[target + 1];
return helper(0, target, memo);
}
public int helper(int step, int target, int[] memo){
if (memo[step] != 0){
return memo[step];
}
if(step == target){
return 1;
}
if(step > target){
return 0;
}
memo[i] = helper(step + 1, target, memo) + helper(step + 2, target, memo);
return memo[i];
}
3. 動態(tài)規(guī)劃
Intuitive:
那么就來到高大上的DP了当凡，曾經(jīng)有一度我都認(rèn)為按照我的水平面試如果遇到DP的題就基本可以跪了。雖然現(xiàn)在依然有點(diǎn)怵纠俭，但是發(fā)現(xiàn)DP他不是玄學(xué)沿量，一上來就給你整個(gè)高大上的狀態(tài)轉(zhuǎn)移方程，自然會一臉懵逼冤荆。但是欧瘪，如果了解了DP是怎么從暴力遞歸，記憶化搜索一步步進(jìn)化而來的匙赞，那么就可以不再害怕DP這個(gè)磨人的小妖精啦佛掖。不記得從哪里看到一句話，DP是一種思想而不是算法涌庭，嗯芥被，所以要想的多...
DP的本質(zhì)就是當(dāng)前結(jié)果依賴于之前結(jié)果，或者說子問題坐榆。那么我們在第i步時(shí)候的方法數(shù)就依賴于之前走的步數(shù)拴魄，在這道題就是:
dp[i] = dp[i - 1] + dp[i - 2]
Edge Cases:
那么edge cases 就很明顯了，總不能讓index小于0吧╮(－_－)╭。
- dp[1] = 1
- dp[2] = 2
Code:
TC: O(n) SC:O(n)
public int climbStairs(int target){
if (target == 1 || target == 2){
return target;
}
int[] dp = new int[target + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= target; i++){
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[target];
}
其實(shí)關(guān)于動態(tài)規(guī)劃和記憶搜索的區(qū)別匹中，我并不是分的很清楚夏漱，有的資料說一個(gè)是top down一個(gè)是bottom up。嗯顶捷，那么對于倒著填的DP又該怎么解釋呢挂绰？在這里mark一下，以后找找資料做個(gè)記憶化搜索和動態(tài)規(guī)劃的比較v(￣︶￣)y
其實(shí)從狀態(tài)轉(zhuǎn)移方程不難看出來服赎，結(jié)果dp[i]只依賴于前兩個(gè)數(shù)dp[i - 1]和dp[i - 2]葵蒂。所以在不要求打印路徑的情況下，我們真的需要一個(gè)O(n)的空間么重虑？是不是只要維護(hù)兩個(gè)變量滾動更新就好了践付？那么之前的DP解法可以進(jìn)一步簡化了。
Code:
TC: O(n) SC:O(1)
public int climbStairs(int target){
if (target == 1 || target == 2){
return target;
}
int pre1 = 1;
int pre2 = 2;
for (int i = 3; i <= target; i++){
int temp = pre1 + pre2
pre1 = pre2;
pre2 = temp;
}
return pre2;
}
4. 矩陣解法
Here comes the fun part~~~ (=￣ω￣=)
其實(shí)這部分才是我寫這篇又臭又長的博文的動機(jī)所在缺厉，那么就讓我試試用我捉襟見肘的語言表達(dá)能力和慘不忍睹的數(shù)學(xué)功底能不能解釋清楚吧...
從之前的DP解法我們知道遞推公式是這樣滴：
f(n) = f(n - 1) + f(n - 2)
那么對于這樣一個(gè)二階的遞推公式我們能不能借用一個(gè)二階的矩陣來表示這個(gè)遞推關(guān)系呢永高？試一試哈,設(shè)我們的謎之矩陣為
我們想促成這樣的一個(gè)表達(dá)式：
已知的一些關(guān)系為：
f(1) = 1
f(2) = 2
f(3) = 3
f(4) = 5
把這些已知的數(shù)代入這個(gè)遞推關(guān)系式中：
四個(gè)未知數(shù)四個(gè)方程，那么可以求出謎之矩陣為
那么通式為：
通式右邊的部分我們可以繼續(xù)用公式替換：
例如把：
代入通式提针，得：
以此類推通式可以化簡為：
那么原問題就可以被轉(zhuǎn)化成求二階矩陣n - 2次方的問題了乏梁。先不考慮矩陣，從最簡單的來哈关贵，如果求一個(gè)數(shù)的n次方，讓你用O(lgn)的算法求出卖毁，最直接的想法是什么揖曾？沒錯轉(zhuǎn)化成二進(jìn)制計(jì)算。
舉個(gè)例子, 求10 ^ 35, 可以分解為：
而35轉(zhuǎn)化為二進(jìn)制為：
不難看出亥啦，只有在二進(jìn)制位上是1的時(shí)候我們才需要乘以該位對應(yīng)的數(shù)值炭剪，而遇到為0的情況就直接skip，運(yùn)算次數(shù)減少了很多呀翔脱。
那么對于矩陣的乘法也是一樣的道理滴奴拦。最多需要你implement一個(gè)計(jì)算兩個(gè)矩陣相乘的helper function 而已。時(shí)間復(fù)雜度分析也很清楚了届吁，矩陣的n次方可以由矩陣n/2次方的平方得出错妖，以此類推可以有這樣一個(gè)recrusion tree：
樹的高度是lg(n), 那么我們需要做的乘法是也就是lg(n)次。
Edge Cases:
與之前差不多
Code:
TC: O(lg(n)) SC:O(1)
public int climStairs(int target){
if(target < 1){
return 0;
}
if (target == 1 || target == 2){
return target;
}
int[][] matrix = {{1, 1},{1, 0}};
int[][] res = matrixPow(matrix, target - 2);
//別忘記乘以最開始的f(2) 與 f(1)
return res[0][0] * 2 + res[0][1] * 1;
}
//計(jì)算矩陣 n 次方
public int[][] matrixPow(int[][] matrix, int n){
int r = matrix.length;
int c = matrix[0].length;
int[][] res = new int[r][c];
//單位矩陣
for (int i = 0; i < r; i++){
res[i][i] = 1;
}
int[][] placeHolder = matrix;
for(; n > 0; n >>>= 1){
if ((n & 1) == 1){
res = matrixMulti(res, placeHolder);
}
placeHolder = matrixMulti(placeHolder, placeHolder);
}
return res;
}
//計(jì)算兩矩陣相乘
public int[][] matrixMulti(int[][] m1, int[][] m2){
int m1Row = m1.length;
int m1Col = m1[0].length;
int m2Col = m2[0].length;
int[][] res = new int[m1Row][m2Col];
for (int i = 0; i < m1Row; i++){
for (int k = 0; k < m1Col; k++){
if (m1[i][k] != 0){
for (int j = 0; j < m2Col; j++){
if(m2[k][j] != 0){
res[i][j] += m1[i][k] + m2[k][j];
}
}
}
}
}
return res;
}
5. 斐波那契公式解法
最后一種是借助用斐波那契數(shù)列的解來解題疚沐，更多數(shù)學(xué)...
為了方便用二元一次方程的通解我們把斐波那契的公司小小改動一下暂氯，表達(dá)的意思還是一樣的哈:
則原方程轉(zhuǎn)化為：
兩邊都除以相同項(xiàng)得：
套用二元一次方程通解得：
則f(n) 可以寫為：
代入已知的f(0) = 0, f(1) = 1等... 可得：
代入之前的公式得：
大功告成~ 所以code也就是直接套用這個(gè)公式一下就好，偷個(gè)懶不寫了亮蛔。另外從這個(gè)公式也不難看出斐波那契數(shù)列問題如果用brute force方法解的話復(fù)雜度是2^n的痴施。
補(bǔ)充：
嗯，之所以花時(shí)間來總結(jié)這個(gè)題，就是因?yàn)楹芏郉P的題其實(shí)本質(zhì)就是個(gè)爬樓梯問題辣吃，或者說本質(zhì)就是斐波那契數(shù)列問題动遭。那么只要我們了解了這個(gè)方法論之后，那么在遇到類似的題目就可以見招拆招神得，萬變不離其宗啦厘惦。
舉個(gè)??：
有一對兔子，每個(gè)月都生一對兔子循头，小兔子長到第三個(gè)月后每個(gè)月又生一對兔子绵估，假如兔子都不死，問每個(gè)月的兔子總數(shù)為多少卡骂？
貢獻(xiàn)于第n個(gè)月的兔子數(shù)量的是f(n - 1) + f(n - 3)
遞推公式是 f(n) = f(n - 1) + f(n - 3)
那么三階遞推公式就可以試試用三階遞推矩陣表示了国裳，其余的步驟就大同小異啦。
Reference:
https://discuss.leetcode.com/topic/30625/easiest-java-solution
https://leetcode.com/problems/climbing-stairs/solution/
