动态规划实例——换零钱的方法数（详解版）
原写了 Java 版本的如何求解换钱的方法数，近期进行了一些细节上的补充，以及部分错误更正，将语言换为了 C++ 语言。
基础题目
假设你现在拥有不限量的 1 元、5 元、10 元面值纸币，路人甲希望找你换一些零钱，路人甲拿出的是一张 100 元面值的纸币，试求总共有多少种换零钱的方法？
分析：因为总共只有 3 种面值小额纸币，所以将所有可能进行枚举，直接暴力解决即可。
#include<bits/stdc++.h>
using namespace std;
int slove() {
int ans = 0;
// 10 元张数
for(int i = 0; i <= 10; i++) {
// 5 元张数
for(int j = 0; j <= 20; j++) {
// 1 元张数
for(int k = 0; k <= 100; k++) {
int cur = i*10 + j*5 + k*1;
if(cur == 100) {
ans++;
}
}
}
}
return ans;
}
int main()
{
cout<<slove();
}
递归求解
基础题目中是拥有固定种类的小额纸币，即使再多几种小额纸币也没关系，大不了在嵌套几个循环就能解决。现在需要将题目的难度加大一点，改为小额纸币的种类和需要换零钱的总额由用户输入，即小额纸币种类和总额都不在固定，那么如何解决？
输入共有三行：
- 第一行：小额纸币种类数量
- 第二行：不同小额纸币的面值
- 第三行：需要换零钱的总额
分析：虽然现在种类和总额都是变量了，但是上文中的基础版本还是被包含在此问题中，所以我们还是以上文中的 1 元、5 元、10 元换 100 元进行分析，找一找除了枚举是否还有其他方法解决。
我们先固定一种零钱的数量，剩下的钱用剩余零钱去兑换，即：
- 用 0 张 1 元换，剩下的用 5、10 元换，最终方法数为 count0；
- 用 1 张 1 元换，剩下的用 5、10 元换，最终方法数为 count1；
- ......
- 用 100 张 1 元换，剩下的用 5、10 元换，最终方法数为 count100；
那么最终换钱的方法综述即为count0 + count1 + count2 + ... + count100。
上面的分析中，我们把原来的大问题拆为了 101 个小问题，且每一个小问题都有很相似的地方，即：
- 求用 5、10 元换 100 元的方法数
- 求用 5、10 元换 95 元的方法数
- ......
- 求用 5、10 元换 0 元的方法数
如果我们对这 101 个小问题再进行同样思路的分析，即再固定 5 元零钱的数量，那么就能把问题划分成了规模更小，但问题类型一样的小小问题。即递归的思路，可以写出如下代码。
#include<bits/stdc++.h>
using namespace std;
// money 表示所有小额纸币的面值
// len 表示 money 数组的长度，即：小额纸币种类
// index 表示上文分析中的当前固定第几张
// target 表示现在要兑换的钱的总额
int slove(int money[], int len, int index, int target) {
int ans = 0;
if(index == len) {
ans = target == 0 ? 1 : 0;
} else {
for(int i = 0; i*money[index] <= target; i++) {
// 剩余待换零钱的总额
int cur_total = target-(i * money[index]);
ans = ans + slove(money, len, index+1, cur_total);
}
}
return ans;
}
int main()
{
int m, target;
int money[1000]; // 零钱具体面值
cin>>m; // 零钱种类
for(int i = 0; i < m; i++){
cin>>money[i];
}
cin>>target; // 兑换总额
cout<<slove(money, m, 0, target);
}
优化递归
可以发现上文所写的递归代码存在大量的重复过程，比如下面两种情况，后面所求的子问题是完全一样的，导致程序运行时间的浪费。
- 已经使用了 5 张 1 元、0 张 5 元，剩下的 95 元用 5 元和 10 元兑换
- 已经使用了 0 张 1 元、1 张 5 元，剩下的 95 元用 5 元 和 10 元兑换
既然前面已经求解过相同的子问题了，那么我们是否可以在第一次求解的时候，将计算结果保存下来，这样下次遇到相同子问题的实际，直接查出来用就可以，省去再次求解的时间。
#include<bits/stdc++.h>
using namespace std;
// 用于存储子问题的解
int val_map[1000][1000] = { 0 };
// 0 表示该子问题没有算过
// -1 表示算过，但该子问题无解
// 其它值，即此子问题的方法数
int slove(int money[], int len, int index, int target) {
int ans = 0;
if(index == len) {
ans = target == 0 ? 1 : 0;
} else {
for(int i = 0; i*money[index] <= target; i++) {
// 剩余待换零钱的总额
int cur_total = target-(i * money[index]);
int pre_val = val_map[index+1][cur_total];
// 如果 val 为 0，说明该子问题没有被计算过
if(pre_val == 0) {
ans = ans + slove(money, len, index+1, cur_total);
} else {
ans += pre_val == -1 ? 0 : pre_val;
}
}
}
// 存储计算结果
val_map[index][target] = ans == 0 ? -1 : ans;
return ans;
}
int main()
{
int m, target; // 零钱种类
int money[1000]; // 零钱具体面值
cin>>m;
for(int i = 0; i < m; i++){
cin>>money[i];
}
cin>>target;
cout<<slove(money, m, 0, target);
}
动态规划
上面对递归的优化方案已经能看出来动态规划的影子了，沿着前文先计算再查表的思路继续思考，我们能否提前把所有子问题都计算出答案，对每个子问题都进行查表解决。也即将最初的递归方案改为循环的实现。
所有的递归都能改为循环实现
#include<bits/stdc++.h>
using namespace std;
// 用于存储子问题的解
// val_map[i][j] 表示用 money[0...i] 的小面额零钱组成 j 元的方法数
int val_map[1000][1000] = { 0 };
int slove(int money[], int len, int target) {
// 第一列表示组成 0 元的方法数，所以为 1
for (int i = 0; i < len; i++) {
val_map[i][0] = 1;
}
// 第一行表示只使用 money[0] 一种钱币兑换钱数为i的方法数
// 所以是 money[0] 的倍数的位置为 1，否则为 0
for (int i = 1; money[0]*i <= target; i++) {
val_map[0][money[0]*i] = 1;
}
for (int i = 1; i < len; i++) {
for (int j = 1; j <= target; j++) {
for (int k = 0; j >= money[i]*k; k++) {
/*
val_map[i][j] 的值为：
用 money[0...i-1] 的零钱组成 j 减去 money[i] 的倍数的方法数
因为相比 val_map[i-1][j]，只是多了一种零钱的可选项
*/
val_map[i][j] += val_map[i-1][j-money[i]*k];
}
}
}
return val_map[len-1][target];
}
int main()
{
int m, target; // 零钱种类
int money[1000]; // 零钱具体面值
cin>>m;
for(int i = 0; i < m; i++){
cin>>money[i];
}
cin>>target;
cout<<slove(money, m, target);
}
动归优化
在上文第一版动态规划代码的优化中已经能发现，其实val_map[i][j]的值由两部分组成，分别为：
- 用 money[0...i-1] 的零钱组成换 j 元的方法数
- 用 money[0...i-1] 的零钱换 j-money[i]*k（k=1,1,2,3....）元的方法数之和
对于第二种情况来说，其累加值实际上就是val_map[i][j-money[i]]，即用money[0...i]的零钱换 j-money[i]元的方法数。至于具体为什么累加值与val_map[i][j-money[i]]相等，我们可以借助递归方法时的分析方式进行理解。
用 money[0...i-1] 的零钱组成换 j 元的方法数对应：
- 用 0 张 money[i] 换，剩下的用 money[0...i-1] 换
用 money[0...i-1] 的零钱换 j-money[i]*k（k=1,1,2,3....）元的方法数之和对应：
- 用 1 张 money[i] 换，剩下的用 money[0...i-1] 换
- 用 2 张 money[i] 换，剩下的用 money[0...i-1] 换
- ......
所以第二部分的值即为val_map[i][j-money[i]]。依据此处的分析，我们可以在原有基础上去掉第三层循环，减少程序运行所花费的时间。
#include<bits/stdc++.h>
using namespace std;
int val_map[1000][1000] = { 0 };
int slove(int money[], int len, int target) {
for (int i = 0; i < len; i++) {
val_map[i][0] = 1;
}
for (int i = 1; money[0]*i <= target; i++) {
val_map[0][money[0]*i] = 1;
}
for (int i = 1; i < len; i++) {
for (int j = 1; j <= target; j++) {
val_map[i][j] = val_map[i-1][j];
// 此处需要比较 j 的大小，防止数组越界
// 注意条件时 >= ，否则少计算 j 刚好为 money[i] 的情况
if(j >= money[i]) {
val_map[i][j] += val_map[i][j-money[i]];
}
}
}
return val_map[len-1][target];
}
int main()
{
int m, target; // 零钱种类
int money[1000]; // 零钱具体面值
cin>>m;
for(int i = 0; i < m; i++){
cin>>money[i];
}
cin>>target;
cout<<slove(money, m, target);
}
空间压缩
仔细观察能发现，每一次更新val_map[i][j]的值时，它只依赖于上一行和当前这一行前面的元素。对于我们所求解的问题来说，它仅要求我们给出最终的答案即可，那么前面存储中间结果的那些元素实际上就会空间的浪费，因此我们可以思考一下如何在空间上进行压缩。
实际上我们只需要定义一个一维的数组，采用一些技巧对该数组进行滚动更新，按照合适的方向去更新数组，同样可以达到上面使用二维数组的效果。
#include<bits/stdc++.h>
using namespace std;
int val_map[1000] = { 0 };
int slove(int money[], int len, int target) {
// 第一行，只用 money[0] 换零钱
// 所以只能换 money[0] 倍数的钱
for (int i = 0; money[0]*i <= target; i++) {
val_map[money[0] * i] = 1;
}
for (int i = 1; i < len; i++) {
for (int j = 1; j <= target; j++) {
if(j >= money[i]) {
// 在进行下面一步前 val_map[j] 的值就已经是 val_map[i-1][j] 了
val_map[j] += val_map[j-money[i]];
}
}
}
return val_map[target];
}
int main()
{
int m, target; // 零钱种类
int money[1000]; // 零钱具体面值
cin>>m;
for(int i = 0; i < m; i++){
cin>>money[i];
}
cin>>target;
cout<<slove(money, m, target);
}
投递淘天集团等公司10个岗位 >