笔者最近一直在刷动态规划方面算法，昨天 Soul 笔试算法题遇到了一个经典动态规划问题，在此做个记录。 题目：用火柴拼接数字，数字 1-9 所需火柴数量分别为：2，5，5，4，5，6，3，7，6，现在给定一个数字，表示总共火柴数量 n，给定一个数组 arr,表示只能组合出该数字。如：n = 5, arr = [1, 3, 6]，则表示，用5根火柴将1 ，3，6 中的某些数字进行组合，每一个数字可以被多次使用，得到最终结果。写一个方法，返回值为在 n 根火柴的条件下，arr 数组中，能被拼接出的最大值为多少？（数值在 int 范围之内）
思路：本题是经典动态规划问题，每一个数字都有对应的代价，也可以获得一定的“收益”，所以，本题的模型可以参考“打工问题”，较为复杂的是，本题“收益”是要对数字进行“最大化叠加”得到结果（例如：34215 最大化之后为：54321），在细节的点上更加复杂。
首先，题目给定了需要组合的目标数组，并且给了组合每个数对应的火柴代价，并且，我们一定需要对目标数和火柴代价进行综合排序——总体以花费火柴数递增的方式进行排序，如果花费货叉数量一样，则按照数字递减的方式排序。这个排序也是用到了一点小“贪心”策略，我当然希望用最少的火柴凑出最大的数，如果我现在用剩余的火柴都无法凑出最小需要花费的火柴数量，那么，这种方案就结束了。
我们需要定义内部类：
// 封装了 数值 & 该数值花费的代价
static class Pay {
int num;
int cost;
public Pay() {
}
public Pay(int num, int cost) {
this.num = num;
this.cost = cost;
}
@Override
public String toString() {
return "Pay{" +
"num=" + num +
", cost=" + cost +
'}';
}
}
接着我们需要定义比较器，在 cost 不同的情况下，按照升序排序；在 cost 一样的情况下，按照降序 num 排序
// 自定义比较器，比较 pay 对象花费代价 // 在花费代价相同的情况下，比较数字大小 static class MyComparator implements Comparator{ @Override public int compare(Pay o1, Pay o2) { return (o1.cost != o2.cost) ? (o1.cost - o2.cost) : (o2.num - o1.num); } }
然后就可以开始暴力递归了！
// 初始版本，纯暴力递归
private static int getMaxNums(int n, int[] arr) {
// arr = [1, 3, 6]
// pay = [2, 5, 6]
int[] cost = {2, 5, 5, 4, 5, 6, 3, 7, 6};
Pay[] pays = new Pay[arr.length];
// 实体对象封装
for (int i = 0; i < arr.length; i++) {
pays[i] = new Pay();
pays[i].num = arr[i];
pays[i].cost = cost[arr[i] - 1];
}
// 对 Pay 数组进行排序，按照花费代价排序
Arrays.sort(pays, new MyComparator());
String ans = process(n, pays, 0, n);
return (ans != null && !"".endsWith(ans)) ? Integer.valueOf(ans) : -1;
}
private static String process(int n, Pay[] pays, int index, int rest) {
// base case
if (index == pays.length) {
return "";
}
if (pays[index].cost > rest) {
return "";
}
String ans = "";
// rest 可以继续凑下去，继续递归
// 对 index 位置，可以凑 0 - (rest / pays[i].cost) 次
for (int i = 0; i <= rest / pays[index].cost; i++) {
String next = process(n, pays, index + 1, rest - i * pays[index].cost);
// 对 cur 进行排序，凑出当前最好的结果
String temp = "";
for (int j = 0; j < i; j++) {
temp = temp + String.valueOf(pays[index].num);
}
String value = temp + next;
// 排序
String result = sumSort(value);
if (!"".equals(result) && !"".equals(ans)) {
ans = String.valueOf(Math.max(Integer.valueOf(ans)
, Integer.valueOf(result)));
} else if (!"".equals(result) && "".equals(ans)) {
ans = result;
} else {
ans = result;
}
}
return ans;
}
我们将暴力递归改成记忆化搜索，只需要家一个二维的 dp 即可
// 缓存
private static int getMaxNumsCache(int n, int[] arr) {
// arr = [1, 3, 6]
// pay = [2, 5, 6]
int[] cost = {2, 5, 5, 4, 5, 6, 3, 7, 6};
Pay[] pays = new Pay[arr.length];
for (int i = 0; i < arr.length; i++) {
pays[i] = new Pay();
pays[i].num = arr[i];
pays[i].cost = cost[arr[i] - 1];
}
// 对 Pay 数组进行排序，按照花费代价排序
Arrays.sort(pays, new MyComparator());
String[][] dp = new String[pays.length + 1][n + 1];
for (int i = 0; i < dp.length; i++) {
for (int j = 0; j < dp[i].length; j++) {
dp[i][j] = "-1";
}
}
String ans = CacheProcess(n, pays, 0, n, dp);
return (ans != null && !"".endsWith(ans)) ? Integer.valueOf(ans) : -1;
}
private static String CacheProcess(int n, Pay[] pays, int index, int rest, String[][] dp) {
// base case
if (index == pays.length) {
return "";
}
if (pays[index].cost > rest) {
return "";
}
// 命中缓存
if (!"-1".equals(dp[index][rest])) {
return dp[index][rest];
}
String ans = "";
// rest 可以继续凑下去，继续递归
// 对 index 位置，可以凑 0 - (rest / pays[i].cost) 次
for (int i = 0; i <= rest / pays[index].cost; i++) {
String next = process(n, pays, index + 1, rest - i * pays[index].cost);
// 对 cur 进行排序，凑出当前最好的结果
String temp = "";
for (int j = 0; j < i; j++) {
temp = temp + String.valueOf(pays[index].num);
}
String value = temp + next;
// 排序
String result = sumSort(value);
if (!"".equals(result) && !"".equals(ans)) {
ans = String.valueOf(Math.max(Integer.valueOf(ans)
, Integer.valueOf(result)));
} else if (!"".equals(result) && "".equals(ans)) {
ans = result;
} else {
ans = result;
}
}
return dp[index][rest] = ans;
}
然后再将暴力递归改为经典动态规划：
// 经典动态规划
private static int getMaxNumsDP(int n, int[] arr) {
// arr = [1, 3, 6]
// pay = [2, 5, 6]
int[] cost = {2, 5, 5, 4, 5, 6, 3, 7, 6};
Pay[] pays = new Pay[arr.length];
for (int i = 0; i < arr.length; i++) {
pays[i] = new Pay();
pays[i].num = arr[i];
pays[i].cost = cost[arr[i] - 1];
}
// 对 Pay 数组进行排序，按照花费代价排序
Arrays.sort(pays, new MyComparator());
String[][] dp = new String[pays.length + 1][n + 1];
for (int i = 0; i < dp[0].length; i++) {
dp[pays.length][i] = "";
}
processDP(n, pays, dp);
return Integer.valueOf(dp[0][n]);
}
private static void processDP(int n, Pay[] pays, String[][] dp) {
for (int index = pays.length - 1; index >= 0; index--) {
for (int rest = n; rest >= 0; rest--) {
if (pays[index].cost > rest) {
dp[index][rest] = "";
} else {
String ans = "";
// rest 可以继续凑下去，继续递归
// 对 index 位置，可以凑 0 - (rest / pays[i].cost) 次
for (int i = 0; i <= rest / pays[index].cost; i++) {
String next = process(n, pays, index + 1, rest - i * pays[index].cost);
// 对 cur 进行排序，凑出当前最好的结果
String temp = "";
for (int j = 0; j < i; j++) {
temp = temp + String.valueOf(pays[index].num);
}
String value = temp + next;
// 排序
String result = sumSort(value);
if (!"".equals(result) && !"".equals(ans)) {
ans = String.valueOf(Math.max(Integer.valueOf(ans)
, Integer.valueOf(result)));
} else if (!"".equals(result) && "".equals(ans)) {
ans = result;
} else {
ans = result;
}
}
dp[index][rest] = ans;
}
}
}
}
总结：本题在其他题目中出现过类似的问题，在 dp 思路和模型层面还是比较容易想到的，问题在于每一次统计最大值这个问题，笔者将数据变为 String 类型，方便统计计算，但是，在比较过程中较为不方便。
