Dynamic Programming

??Dynamic Programming是五大常用演算法策略之一，簡稱DP，譯作中文是“動態規劃”，可就是這個聽起來高大上的翻譯坑苦了無數人，因為看完這個演算法你可能會覺得和動態規劃根本沒太大關系，它對“動態”和“規劃”都沒有太深的體現，
??舉個最簡單的例子去先淺顯的理解它，有個大概的雛形，找一個陣列中的最大元素，如果只有一個元素，那就是它，再往陣列里面加元素，遞推關系就是，當你知道當前最大的元素，只需要拿當前最大元素和新加入的進行比較，較大的就是陣列中最大的，這就是典型的DP策略，將小問題的解保存起來，解決大問題的時候就可以直接使用，
??剛剛說的如果還是感覺有點迷糊，不用慌，下面幾個簡單的小栗子讓你明白這句話的意思，

0、Fibonacci再討論(易)

1、求解路徑個數(易)

2、小青蛙跳臺階再討論(易)

3、最長公共子序列問題(偏難)

4、0-1背包問題(一般)

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 method
private 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);
        }
    }
}

標籤：其他

上一篇：有什么其他方法可以快速的求出這ab兩端的等效電阻。（不用萬用表測量的方法）

下一篇：有什么方法可以更快速的求出ab兩端的等效電阻（除了用萬用表測量）