1、前言

如上一篇文章结尾，提到的动态规划读表，本文就围绕动态规划读表展开。

2、零钱问题

题目

考虑仅用1分、5分、10分、25分和50分这5种硬币支付某一个给定的金额。
例如需要支付11分钱，
有一个1分和一个10分、
一个1分和两个5分、
六个1分和一个5分、
十一个1分这4种方式。
请写一个程序，
1）计算一个给定的金额有几种支付方式。
2）使用硬币最少的数量
3）使用硬币最少的数量时的组合
注：假定支付0元有1种方式

要求1，2就是我们之前遇到的动态规划，只要结果，不求过程。而3的提问，就是索求过程，由于我们已经记录了整个递推的流程，因此，我们可以按照一定的规律找到整个流程，后面再说。

1）计算一个给定的金额有几种支付方式

暴力递归版本

    public static long exchange1(int[] coins, int aim) {
        return process(coins, 0, aim, 0);
    }
    // index代表取arr[index]的数，进行取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;
    }

动态规划思路：
创建一个二维数组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]的整数倍时，有1种方法
        for (int i = 1; i <= aim; i++) {
            if(i % coins[0] == 0){
                dp[0][i]=1;//第一行中能够被arr[0]整除的数，即可以被换钱，记为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）使用硬币最少的数量

定义二维数组dp[coins.length][aim + 1]，dp[i][j]表示在coins[0..i]组成j的最小硬币数量。
那么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的最小硬币数量
        int[][] dp = new int[coins.length][aim + 1];
        // 填写第一行，当j == coins[0]的整数倍时，有1种方法
        for (int i = 1; i <= aim; i++) {
            if(i % coins[0] == 0){
                dp[0][i] = i / coins[0];//第一行中能够被arr[0]整除的数，即可以被换钱，记为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）使用硬币最少的数量时的组合

由于存在以下转换方程:
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]，继续往上找，直至i==0，图解如下，蓝色方块就是最优组合：

代码实现，在第二问的基础上，添加了寻找最佳组合的代码

    public static int exchange3(int[] coins, int aim) {
        // dp[i][j]表示在coins[0..i]组成j的最小硬币数量
        int[][] dp = new int[coins.length][aim + 1];
        // 填写第一行，当j == coins[0]的整数倍时，有1种方法
        for (int i = 1; i <= aim; i++) {
            if(i % coins[0] == 0){
                dp[0][i] = i / coins[0];//第一行中能够被arr[0]整除的数，即可以被换钱，记为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"都是
最长公共子序列，返回哪一个都行。

算法实现

创建一个二维数组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]相等的字符，
                // 那么接下来的区间，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]相等的字符，
                // 那么接下来的区间，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]);
对应的代码如下：

        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]基础上 + 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表已经填满了，接下来要开始读表了。由以上的递推式，我们可知，初始时，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]相等的字符，
                // 那么接下来的区间，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]相等的字符，
                // 那么接下来的区间，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]基础上 + 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));
    }

总结

以上就是动态规划的读表题，其实不必特别在意如何推出找表的公式。基本上来说，就是一直往上找，然后再往左找（表述不好，请谅解）。那么，这就是动态规划的最后一篇了，想更加深刻的理解DP，只能做多点题目，增加点感觉了~