Dynamic Programming
Dynamic Programming是五大常用算法策略之一，簡稱DP，譯作中文是「動態規劃」，可就是這個聽起來高大上的翻譯坑苦了無數人，因為看完這個算法你可能會覺得和動態規劃根本沒太大關係，它對「動態」和「規劃」都沒有太深的體現。
舉個最簡單的例子去先淺顯的理解它，有個大概的雛形，找一個數組中的最大元素，如果只有一個元素，那就是它，再往數組裡面加元素，遞推關係就是，當你知道當前最大的元素，只需要拿當前最大元素和新加入的進行比較，較大的就是數組中最大的，這就是典型的DP策略，將小問題的解保存起來，解決大問題的時候就可以直接使用。
剛剛說的如果還是感覺有點迷糊，不用慌，下面幾個簡單的小栗子讓你明白這句話的意思。
0、Fibonacci再討論(易)
2、小青蛙跳台階再討論(易)
3、最長公共子序列問題(偏難)
Fibonacci再討論
第一個數是1，第二個數也是1，從第三個數開始，後面每個數都等於前兩個數之和。要求：輸入一個n，輸出第n個斐波那契數。
還是我們上節討論遞歸與分治策略時候舉的第一個例子——Fibonacci數列問題，它實在太經典了，所以將其反覆拿出來說。
我們如果深入分析一下上節說過的遞歸方法解決Fibonacci數列，就會發現出現了很多重複運算，比如你在計算f(5)的時候，你要計算f(4)和f(3),計算f(4)又要計算(3)和f(2),計算f(3)，又要計算f(2)和f(1),看下面這個圖
對f(3)和f(2)進行了重複運算，這還是因為5比較小，如果要計算f(100),那你可能要等到天荒地老它還沒執行完（手動滑稽），感興趣的朋友可以試試，反正我已經試過了。
public static int fibonacci(int n){//遞歸解法 if(n == 1) return 1; else if(n == 2) return 1; else return fibonacci(n - 1) + fibonacci(n - 2);}上面就是遞歸的解法，代碼看著很簡單易懂，但是算法複雜度已經達到了O(2^n),指數級別的複雜度，再加上如果n較大會造成更大的棧內存開銷，所以非常低效。
我們再來說說DP策略解決這個問題
我們知道導致這個算法低效的根本原因就是遞歸棧內存開銷大，對越小的數要重複計算的次數越多，那既然我們已經將較小的數，諸如f(2),f(3)...這些計算過了，為什麼還要重複計算呢，這時就用到了DP策略，將計算過的f(n)保存起來。我們看看代碼：
/** * 對斐波那契數列求法的優化：如果單純使用遞歸，那重複計算的次數就太多了，為此，我們對其做一些優化 * 假設最多計算到第100個斐波那契數 * 用arr這個數組來保存已經計算過的Fibonacci數，以確保不會重複計算某些數 */private static int arr[] = new int[100];public static int Fibonacci(int n){ if(n <= 2){ return 1; }else{ if(arr[n] != 0) //判斷是否計算過這個f(n) return arr[n]; else{ arr[n] = Fibonacci(n-1)+Fibonacci(n-2); return arr[n]; } }}arr數組初始化為0，arr[i]就表示f(i),每次先判斷arr[i]是否為0，如果為0則表示未計算過，則遞歸計算，如果不為0，則表示已經計算過，那就直接返回。
這樣的好處避免了很大程度上重複的計算，但是對棧內存的開銷雖然有減小但還不是很顯著，因為只要有遞歸，棧內存就免不了有較大開銷。所以針對Fibonacci數列我們還有一個遞推的方式來計算，其實這也符合DP策略的思想，都是將計算過的值保存起來。
//甚至可以使用遞推來求解Fibonacci數列public static int fibonacci(int n){ if(n <= 2) return 1; int f1 = 1, f2 = 1, sum = 0; for(int i = 3; i <= n; i++){ sum = f1+f2; f1 = f2; f2 = sum; } return sum;}求解路徑個數
一個機器人每次只能向右或者下走一步，問它試圖到達右下角「Finish」，共有多少條不同的路徑？(7*3的網格)
DP策略類的題最重要是要找狀態轉移方程，恰恰也是最難的一步。
- 1、我們通過這個圖可以看出其實要到達(i,j)也就兩種情況，一種是從(i,j-1)向右走一步到達，另一種是從(i-1,j)向下走一步到達，所以將這兩種情況的路徑數相加就是到(i,j)的所有路徑數。由此列出狀態轉移方程：f(i,j)=f(i-1,j)+f(i,j-1)
- 2、根據DP的思路，將已經計算過的存儲起來並用於後面復用其結果，這裡我們考慮用二維數組來存儲f(i,j)。
- 3、問題規模從小到大計算，大規模的問題復用小規模問題的解進行計算。代碼實現
/** * 此題是求解路徑個數，讓你從(1,1)走到某個特定的位置，求一共有多少種走法 * @param i * @param j * @return */public static int Count_Path(int i, int j){ int result[][] = new int[i][j]; for (int k = 0; k < i; k++) { //將二維數組初始化為1 Arrays.fill(result[k],1); } for (int k = 1; k < i; k++) { for (int l = 1; l < j; l++){ result[k][l] = result[k-1][l]+result[k][l-1]; } } return result[i-1][j-1];}小青蛙跳台階再討論
又是那隻熟悉的青蛙，和上節遞歸與分治中相同的例題，一隻青蛙一次可以跳上1級台階，也可以跳上2級，求該青蛙跳上一個n級的台階共有多少種跳法。詳細思路可以看看上一篇文章——遞歸與分治策略。
我們下面先回顧一下上次用的遞歸算法：
public static int Jump_Floor1(int n){ if(n <= 2){ return n; }else{ //這裡涉及到兩種跳法，1、第一次跳1級就還有n-1級要跳，2、第一次跳2級就還有n-2級要跳 return Jump_Floor1(n-1)+Jump_Floor1(n-2); }}其實和第一個例子斐波那契一樣，之所以把它又拉出來討論，是因為它的遞歸解法中涉及的重複計算實在太多了，我們需要將已經計算過的數據保存起來，以避免重複計算，提高效率。這裡大家可以先自己試著改一下其實和第一個例子的改進方法是一樣的，用一個數組來緩存計算過的數據。
/** * 看完遞歸的方法不要先被它的代碼簡潔所迷惑，可以分析一下複雜度，就會發現有很多重複的計算 * 而且看完這個會發現和Fibonacci的遞歸方法有點像 * @非遞歸 */private static int result[] = new int[100];public static int Jump_Floor2(int n){ if(n <= 2){ return n; }else{ if(result[n] != 0) return result[n]; else{ result[n] = Jump_Floor2(n-1)+Jump_Floor2(n-2); return result[n]; } }}下面將難度做一提升，我們來討論一道DP策略里的經典例題——最長公共子列問題
最長公共子序列問題
給定兩個序列，需要求出兩個序列最長的公共子序列，這裡的子序列不同於字串，字串要求必須是連續的一個串，子序列並沒有這麼嚴格的連續要求，我們舉個例子：
比如A = "LetMeDownSlowly!" B="LetYouDownQuickly!" A和B的最長公共子序列就是"LetDownly!"
比如字符串1：BDCABA；字符串2：ABCBDAB，則這兩個字符串的最長公共子序列長度為4，最長公共子序列是：BCBA
我們設 X=(x1,x2,.....xn) 和 Y={y1,y2,.....ym} 是兩個序列，將 X 和 Y 的最長公共子序列記為LCS(X,Y)，要找它們的最長公共子序列就是要求最優化問題，有以下幾種情況：
- 1、n = 0 || m = 0，不用多說最長的也只能是0，LCS(n,m) = 0
- 2、X(n) = Y(m)，說明當前序列也是相等的，那就給這兩個元素匹配之前的最長長度加一，即LCS(n,m)=LCS(n-1,m-1)+1
- 3、X(n) != Y(m)，這時候說明這兩個元素並沒有匹配上，那所以最長的公共子序列長度還是這兩個元素匹配之前的最長長度，即max{LCS(n-1,m)，LCS(n,m-1)}
由此我們可以列出狀態轉移方程：（用的別人的圖）
我們可以考慮用一個二維數組來保存LCS(n,m)的值，n表示行，m表示列，作如下演示，比如字符串1：ABCBDAB，字符串2：BDCABA；
1、先對其進行初始化操作，即將m=0，或者n=0的行和列的值全填為0
2、判斷發現A != B，則LCS(1,1) = 0，填入其中
3、判斷B == B，則LCS(1,2) = LCS(0,1)+1=1，填入其中
4、判斷B != C，則LCS(1,3)就應該等於LCS(0,3)和LCS(1,2)中較大的那一個，即等於1，通過觀察我們發現現在的兩個序列是{B}和{ABC}在比較，即使現在B != C，但是因為前面已經有一個B和其匹配了，所以長度最少已經為1了，所以當C未匹配時，子序列的最大值是前面的未比較C和B時候的最大值，所以填1
5、再比較到B和B，雖然兩者相等，但是只能是LCS(n-1,m-1)+1，所以還是1，因為一個B只能匹配一次啊，舉個例子：就好像是DB和ABCB來比較，當第一個序列的B和第二個序列的第二個B匹配時，就應該是D和ABC的最長子序列+1，所以如下填表：
6、掌握規律後，我們直接完整填完這個表
代碼實現：
/** * 求最長公共子序列問題 * Talk is cheap, show me the code! * 參考公式(也是最難的一步)： * { 0 i = 0, j = 0 * c[i][j] = { c[i-1][j-1]+1 i,j>0, x[i] == y[i] * { max{c[i-1][j],c[i][j-1]} i,j>0, x[i] != y[i] * 參考書目：算法設計與分析（第四版）清華大學出版社 王曉東 編著 * 參考博客：https://www.cnblogs.com/hapjin/p/5572483.html * 比如A = "LetMeDownSlowly!" B="LetYouDownQuickly!" A和B的最長公共子序列就是"LetDownly!" * @param x * @param y * @Param c 用c[i,j]表示：(x1,x2....xi) 和 (y1,y2...yj) 的**最長**公共子序列的長度 * @return 最長公共子序列的長度 *///maybe private methodprivate static int lcsLength(String x, String y, int[][] c){ int m = x.length(); int n = y.length(); //下面是初始化操作，其實也沒必要，因為Java中默認初始化為0，其他語言隨機應變 for (int i = 0; i <= m; i++) c[i][0] = 0; for (int i = 0; i <= n; i++) c[0][i] = 0; //用一個序列的每個元素去和另一個序列分別比較 for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if(x.charAt(i-1) == y.charAt(j-1)){ //如果遇到相等的，就給序列的上一行上一列的加1 c[i][j] = c[i-1][j-1]+1; }else if(c[i-1][j] >= c[i][j-1]){ //取上一次最大的，保證最長子序列的最長要求 c[i][j] = c[i-1][j]; }else{ c[i][j] = c[i][j-1]; } } } return c[m][n];}0-1背包問題
也是很經典的一道算法題：0-1背包問題說的是，給定背包容量W，一系列物品{weiht,value}，每個物品只能取一件，計算可以獲得的value的最大值。
最優解問題，當然是我們DP，最難的一步還是狀態轉移方程，我們先把方程給出來，再對其進行討論.
m[i][j] = max{ m[i-1][j-w[i]]+v[i] , m[i-1][j]}
m[i][j]表示1,2,...,i個物品，背包容量為j時候的最大value，w[i]表示第i個物品的重量，v[i]表示第i個物品的value
我們用一個二維數組來存儲這個m，i表示1,2,...,i個物品，j表示背包容量
對於每一個物品來說，要計算當前最大的value，分為兩種情況：1、將這個物品放進去，不將這個物品放進去
- 1、我們先考慮不將其放進去， 很好理解，m[i-1][j]就是不將第i個物品放入背包的最大value，不放就是1,2,...,i-1個物品，背包容量為j
- 2、再考慮放進去的情況，既然要將其放進去，那就在背包中給其預先留好位置，m[i-1][j-w[i]]表示在背包中先給第i個物品把地方騰出來，然後背包可用空間就是j-w[i],在這些可用空間裡1,2,...,i-1個物品放的最大value就是m[i-1][j-w[i]]，將其放進去只需要再給加上v[i]即可，即m[i-1][j-w[i]]+v[i]。所以狀態轉移方程就是取放進去和不放進去兩種情況的最大值m[i][j] = max{ m[i-1][j-w[i]]+v[i] , m[i-1][j]}
代碼實現
/** * 此函數用於計算背包中能存放的最大values * @param m m[i][j]用於記錄1,2,...,i個物品在背包容量為j時候的最大value * @param w w數組存放了每個物品的重量weight,w[i]表示第i+1個物品的weight * @param v v數組存放了每個物品的價值value,v[i]表示第i+1個物品的value * @param C C表示背包最大容量 * @param sum sum表示物品個數 * 狀態轉移方程: m[i][j] = max{ m[i-1][j-w[i]]+v[i] , m[i-1][j]} * m[i-1][j]很好理解，就是不將第i個物品放入背包的最大value * m[i-1][j-w[i]]+v[i]表示將第i個物品放入背包，m[i-1][j-w[i]]表示在背包中先給第i個物品把地方騰出來 * 然後背包可用空間就是j-w[i],在這些可用空間裡1,2,...,i-1個物品放的最大value就是m[i-1][j-w[i]],那 * 最後再加上第i個物品的value，就是將第i個物品放入背包的最大value了 */public static void knap(int[][] m, int[] w,int[] v, int C, int sum){ for(int j = 0; j < C; j++){ //初始化 stuttering if(j+1 >= w[0]){ //第一行只有一個物品，如果物品比背包容量大就放進去，否則最大value只能為0 m[0][j] = v[0]; }else{ m[0][j] = 0; } } for(int i = 1; i < sum; i++){ for(int j = 0; j < C; j++){ int a = 0, b = 0; //a表示將第i個物品放入背包的value，b表示不放第i個物品 if(j >= w[i]) a = m[i-1][j-w[i]]+v[i]; b = m[i-1][j]; m[i][j] = (a>b?a:b); } }}