1、前言

如上一篇文章結(jié)尾，提到的動態(tài)規(guī)劃讀表，本文就圍繞動態(tài)規(guī)劃讀表展開。

2、零錢問題

題目

考慮僅用1分、5分、10分、25分和50分這5種硬幣支付某一個給定的金額。
例如需要支付11分錢，
有一個1分和一個10分、
一個1分和兩個5分、
六個1分和一個5分、
十一個1分這4種方式。
請寫一個程序，
1）計算一個給定的金額有幾種支付方式。
2）使用硬幣最少的數(shù)量
3）使用硬幣最少的數(shù)量時的組合
注：假定支付0元有1種方式

要求1，2就是我們之前遇到的動態(tài)規(guī)劃，只要結(jié)果，不求過程。而3的提問，就是索求過程，由于我們已經(jīng)記錄了整個遞推的流程，因此，我們可以按照一定的規(guī)律找到整個流程，后面再說。

1）計算一個給定的金額有幾種支付方式

暴力遞歸版本

    public static long exchange1(int[] coins, int aim) {
        return process(coins, 0, aim, 0);
    }
    // index代表取arr[index]的數(shù)，進行取1張，2張，3張時情況的枚舉
    public static long process(int[] coins, int index, int aim, int alreadySum) {
        long res = 0;
        if (alreadySum == aim) {
            return 1;
        }
        if (index == coins.length) {
            if (alreadySum == aim) {
                return 1;
            }else{
                return 0;
            }
        }

        // 最多有i張 coins[index]
        for(int i = 0; coins[index] * i <= aim; i++) {
            if (i * coins[index] + alreadySum <= aim) {
                res += process(coins, index + 1, aim, i * coins[index] + alreadySum);
            }else {
                break;
            }
            
        }
        return res;
    }

動態(tài)規(guī)劃思路：
創(chuàng)建一個二維數(shù)組dp[coins.length][aim + 1]，i, j代表在coins[0~i]范圍，組成j的方法有幾種。
那么dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]]就是我們的遞推式，表示拿了i這個硬幣的方法組成j的方法 = 不拿這個i硬幣的方法 + dp[i][j - coins[i]]

    public static long exchange(int[] coins, int aim) {
        // i,j代表在0~i范圍，組成j的方法有幾種
        long[][] dp = new long[coins.length][aim + 1];
        // 組成0元的肯定都有1種方法，填寫第一列
        for(int i = 0; i < coins.length; i++) {
            dp[i][0] = 1;
        }
        // 填寫第一行，當j == coins[0]的整數(shù)倍時，有1種方法
        for (int i = 1; i <= aim; i++) {
            if(i % coins[0] == 0){
                dp[0][i]=1;//第一行中能夠被arr[0]整除的數(shù)，即可以被換錢，記為1
            }else{
                dp[0][i]=0;
            }

        }
        for(int i = 1; i < coins.length; i++) {
            for(int j = 1; j <= aim; j++) {
                // 不拿i這個貨幣
                dp[i][j] = dp[i - 1][j];
                // 拿i這個貨幣
                if (j - coins[i] >= 0) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]];
                }
            }
        }
        return dp[coins.length - 1][aim];
    }

2）使用硬幣最少的數(shù)量

定義二維數(shù)組dp[coins.length][aim + 1]，dp[i][j]表示在coins[0..i]組成j的最小硬幣數(shù)量。
那么dp[i][j]可能來自兩個值
1、不拿i這個硬幣，那么dp[i][j]=dp[i - 1][j]
2、那i這個硬幣，那么dp[i][j] = dp[i][j - coins[i]] + 1
然后取上面的較小值，就是dp[i][j]的值了

以coins=[1, 5, 10, 25, 50]，aim=11作為例子，圖解如下：

    public static int exchange3(int[] coins, int aim) {
        // dp[i][j]表示在coins[0..i]組成j的最小硬幣數(shù)量
        int[][] dp = new int[coins.length][aim + 1];
        // 填寫第一行，當j == coins[0]的整數(shù)倍時，有1種方法
        for (int i = 1; i <= aim; i++) {
            if(i % coins[0] == 0){
                dp[0][i] = i / coins[0];//第一行中能夠被arr[0]整除的數(shù)，即可以被換錢，記為1
            }
        }
        for(int i = 1; i < coins.length; i++) {
            for(int j = 1; j <= aim; j++) {
                // 拿i這個貨幣
                if (j - coins[i] >= 0) {
                    int min2 = dp[i][j - coins[i]] + 1;
                    dp[i][j] = Math.min(dp[i - 1][j], min2);
                }else {
                    // 不拿i這個貨幣
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
    }

3）使用硬幣最少的數(shù)量時的組合

由于存在以下轉(zhuǎn)換方程:
1、不拿i這個硬幣，那么dp[i][j]=dp[i - 1][j]
2、那i這個硬幣，那么dp[i][j] = dp[i][j - coins[i]] + 1
然后取上面的較小值，就是dp[i][j]的值了

那么對于dp[i][j]可能是來自dp[i - 1]，或者來自 dp[i][j - coins[i]] + 1，因此，我們先從i = coins.length - 1開始往上找，直至dp[i] != dp[i - 1]，打印當前的coins[i]。
然后j - coins[j]，繼續(xù)往上找，直至i==0，圖解如下，藍色方塊就是最優(yōu)組合：

代碼實現(xiàn)，在第二問的基礎(chǔ)上，添加了尋找最佳組合的代碼

    public static int exchange3(int[] coins, int aim) {
        // dp[i][j]表示在coins[0..i]組成j的最小硬幣數(shù)量
        int[][] dp = new int[coins.length][aim + 1];
        // 填寫第一行，當j == coins[0]的整數(shù)倍時，有1種方法
        for (int i = 1; i <= aim; i++) {
            if(i % coins[0] == 0){
                dp[0][i] = i / coins[0];//第一行中能夠被arr[0]整除的數(shù)，即可以被換錢，記為1
            }
        }
        for(int i = 1; i < coins.length; i++) {
            for(int j = 1; j <= aim; j++) {
                // 拿i這個貨幣
                if (j - coins[i] >= 0) {
                    int min2 = dp[i][j - coins[i]] + 1;
                    dp[i][j] = Math.min(dp[i - 1][j], min2);
                }else {
                    // 不拿i這個貨幣
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        System.out.println("最佳組合：");
        int i = coins.length - 1;
        int j = aim;
        while(j >= 0 && i >= 0) {
            if (i > 0) {
                // 一直往上查找，直至i != i - 1
                while(dp[i][j] == dp[i - 1][j]) {
                    i--;
                    if (i == 0) {
                        break;
                    }
                }
                System.out.print(coins[i] + " ");
                j = j - coins[i];
                if (j <= 0) {
                    break;
                }
            }
        }
        System.out.println();
        return dp[coins.length - 1][aim];
    }

3、最長公共子序列

題目

給定兩個字符串str1和str2，返回兩個字符串的最長公共子序列。
例如，str1="1A2C3D4B56"，str2="B1D23CA45B6A"，"123456"或者"12C4B6"都是
最長公共子序列，返回哪一個都行。

算法實現(xiàn)

創(chuàng)建一個二維數(shù)組dp[str1.length][str2.length]，dp[i][j]代表，在str1[0..i]和str2[0..j]之間最長子序列長度
那么初始的第一列chs1[i] = str1[0~str1.length - 1]，只要chs1[i]一旦=str2[0]，那么[i+1~str1.length - 1]都將有dp[i][0]=1
同理，第一行一旦有chs2[i]=str1[0]，那么[i+1~str2.length - 1]都將有dp[0][i]=1
初始化過程如下：

        char[] chs1 = str1.toCharArray();
        char[] chs2 = str2.toCharArray();
        // dp[i][j]代表，在str1[0..i]和str2[0..j]之間最長子序列長度
        int[][] dp = new int[chs1.length][chs2.length];
        int pre = 0;
        // 填充第一列
        for(int i = 0; i < chs1.length; i++) {
            if(pre == 1) {
                // 一旦之前有和str2[0]相等的字符，
                // 那么接下來的區(qū)間，dp[i][0]都等于1
                dp[i][0] = pre;
            }else {
                if(chs1[i] == chs2[0]) {
                    dp[i][0] = 1;
                    pre = 1;
                }
            }
        }
        // 填充第一行
        pre = 0;
        for(int i = 0; i < chs2.length; i++) {
            if(pre == 1) {
                // 一旦之前有和str2[0]相等的字符，
                // 那么接下來的區(qū)間，dp[i][0]都等于1
                dp[0][i] = pre;
            }else {
                if(chs2[i] == chs1[0]) {
                    dp[0][1] = 1;
                    pre = 1;
                }
            }
        }

那么對于非第一行，第一列的的dp[i][j]存在以下2種情況
1、當chs1[1] == chs2[2]，dp[i][j] = dp[i - 1][j - 1] + 1
2、當chs1[1] != chs2[2]， dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
對應(yīng)的代碼如下：

        for(int i = 1; i < chs1.length; i++) {
            for(int j = 1; j < chs2.length; j++) {
                // 若 chs1[i] == chs2[j]，則在dp[i - 1][j - 1]基礎(chǔ)上 + 1
                if (chs1[i] == chs2[j]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }else {
                    // 若不等，則從dp[i - 1][j]和dp[i][j - 1]之間選一個最大的
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

這時，dp表已經(jīng)填滿了，接下來要開始讀表了。由以上的遞推式，我們可知，初始時，i=str1.len - 1，j=str2.len - 1。
1、dp[i][j]要一直與dp[i - 1][j]比較，直至dp[i][j] !=dp[i - 1][j]
2、dp[i][j]要一直與dp[i][j - 1]比較，直至dp[i][j] != dp[i][j - 1]，此時的str2[j]就是其中一個子字符串。然后j再往左移動1位，再開始以上操作。
以str1="1A2C3D4B56"，str2="B1D23CA45B6A"為例子，圖解如下：

完整代碼如下

    public static void commonLongestSeq(String str1, String str2) {
        char[] chs1 = str1.toCharArray();
        char[] chs2 = str2.toCharArray();
        // dp[i][j]代表，在str1[0..i]和str2[0..j]之間最長子序列長度
        int[][] dp = new int[chs1.length][chs2.length];
        int pre = 0;
        // 填充第一列
        for(int i = 0; i < chs1.length; i++) {
            if(pre == 1) {
                // 一旦之前有和str2[0]相等的字符，
                // 那么接下來的區(qū)間，dp[i][0]都等于1
                dp[i][0] = pre;
            }else {
                if(chs1[i] == chs2[0]) {
                    dp[i][0] = 1;
                    pre = 1;
                }
            }
        }
        // 填充第一行
        pre = 0;
        for(int i = 0; i < chs2.length; i++) {
            if(pre == 1) {
                // 一旦之前有和str2[0]相等的字符，
                // 那么接下來的區(qū)間，dp[i][0]都等于1
                dp[0][i] = pre;
            }else {
                if(chs2[i] == chs1[0]) {
                    dp[0][1] = 1;
                    pre = 1;
                }
            }
        }
        for(int i = 1; i < chs1.length; i++) {
            for(int j = 1; j < chs2.length; j++) {
                // 若 chs1[i] == chs2[j]，則在dp[i - 1][j - 1]基礎(chǔ)上 + 1
                if (chs1[i] == chs2[j]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }else {
                    // 若不等，則從dp[i - 1][j]和dp[i][j - 1]之間選一個最大的
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        for(int i = 0; i < chs1.length; i++) {
            for(int j = 0; j < chs2.length; j++) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }
        
        int i = chs1.length - 1;
        int j = chs2.length - 1;
        char[] results = new char[dp[i][j]];
        int k = dp[i][j] - 1;
        // 查找組成最長子序列的組合
        while(i >= 0 && j >= 0) {
            if(i > 0) {
                // 一直往上找，直至dp[i][j] != dp[i - 1][j]
                while(dp[i][j] == dp[i - 1][j]) {
                    i--;
                    if(i == 0) {
                        break;
                    }
                }
            }
            if (j > 0) {
                // j一直往左找，直至找到dp[i][j] != dp[i][j - 1]
                while(dp[i][j] == dp[i][j - 1]) {
                    j--;
                    if(j == 0) {
                        break;
                    }
                }
                results[k--] = chs2[j];
            }
            j--;
        }
        System.out.println(new String(results));
    }

總結(jié)

以上就是動態(tài)規(guī)劃的讀表題，其實不必特別在意如何推出找表的公式。基本上來說，就是一直往上找，然后再往左找（表述不好，請諒解）。那么，這就是動態(tài)規(guī)劃的最后一篇了，想更加深刻的理解DP，只能做多點題目，增加點感覺了~