【算法】动态规划（三）
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，只能做多点题目，增加点感觉了~
腾讯云开发者
