14.5 完全背包问题¶
在本节中,我们先求解另一个常见的背包问题:完全背包,再了解它的一种特例:零钱兑换。
14.5.1 完全背包问题¶
Question
给定 \(n\) 个物品,第 \(i\) 个物品的重量为 \(wgt[i-1]\)、价值为 \(val[i-1]\) ,和一个容量为 \(cap\) 的背包。每个物品可以重复选取,问在限定背包容量下能放入物品的最大价值。示例如图 14-22 所示。
图 14-22 完全背包问题的示例数据
图解 14-22:完全背包示例:物品可以重复选择
完全背包允许重复选择同类物品;图中给出容量 50 的最优选取方案。
给定 5 种候选物品,背包容量 cap = 50。每种物品的选取次数不限,总重量不能超过 50。本图为容量 50 的独立示例;后文图 14-23 的单行更新改用容量 4、重量 1/2/3 的另一组部分同名、编号与重量都不同的物品数据。
画面左侧表格列出编号 i、重量 wgt[i-1] 与价值 val[i-1],各行用水果图标标识物品。苹果行以浅紫色、香蕉行以浅橙色突出,旁边分别标“×1”“×2”,两条箭头指向右侧标有“背包容量 cap = 50”的背包。下表把物品数据与图示选取数量合并列出;其余物品的 0 表示没有被箭头选中。
图底明确标注“最大价值:290”,并用水果图标说明放入一个苹果和两个香蕉,共占用 50 背包容量。
| 编号 | 物品 | 重量 | 价值 | 图示选取数量 |
|---|---|---|---|---|
| 1 | 苹果 | 10 | 50 | 1 |
| 2 | 香蕉 | 20 | 120 | 2 |
| 3 | 葡萄 | 30 | 150 | 0 |
| 4 | 菠萝 | 40 | 210 | 0 |
| 5 | 西瓜 | 50 | 240 | 0 |
由输入补充计算:总重量为 10 + 2 × 20 = 50,总价值为 50 + 2 × 120 = 290,与图底结论一致。若每件物品只能选一次,同一输入的最优方案是香蕉加葡萄,重 20 + 30 = 50、值 120 + 150 = 270;这一对照由输入推算,未画在本图中。允许重复选择香蕉将最大价值提高到了 290。
1. 动态规划思路¶
完全背包问题和 0-1 背包问题非常相似,区别仅在于不限制物品的选择次数。
- 在 0-1 背包问题中,每种物品只有一个,因此将物品 \(i\) 放入背包后,只能从前 \(i-1\) 个物品中选择。
- 在完全背包问题中,每种物品的数量是无限的,因此将物品 \(i\) 放入背包后,仍可以从前 \(i\) 个物品中选择。
在完全背包问题的规定下,状态 \([i, c]\) 的变化分为两种情况。
- 不放入物品 \(i\) :与 0-1 背包问题相同,转移至 \([i-1, c]\) 。
- 放入物品 \(i\) :与 0-1 背包问题不同,转移至 \([i, c-wgt[i-1]]\) 。
从而状态转移方程变为:
2. 代码实现¶
对比两道题目的代码,状态转移中有一处从 \(i-1\) 变为 \(i\) ,其余完全一致:
def unbounded_knapsack_dp(wgt: list[int], val: list[int], cap: int) -> int:
"""完全背包:动态规划"""
n = len(wgt)
# 初始化 dp 表
dp = [[0] * (cap + 1) for _ in range(n + 1)]
# 状态转移
for i in range(1, n + 1):
for c in range(1, cap + 1):
if wgt[i - 1] > c:
# 若超过背包容量,则不选物品 i
dp[i][c] = dp[i - 1][c]
else:
# 不选和选物品 i 这两种方案的较大值
dp[i][c] = max(dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1])
return dp[n][cap]
/* 完全背包:动态规划 */
int unboundedKnapsackDP(vector<int> &wgt, vector<int> &val, int cap) {
int n = wgt.size();
// 初始化 dp 表
vector<vector<int>> dp(n + 1, vector<int>(cap + 1, 0));
// 状态转移
for (int i = 1; i <= n; i++) {
for (int c = 1; c <= cap; c++) {
if (wgt[i - 1] > c) {
// 若超过背包容量,则不选物品 i
dp[i][c] = dp[i - 1][c];
} else {
// 不选和选物品 i 这两种方案的较大值
dp[i][c] = max(dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1]);
}
}
}
return dp[n][cap];
}
/* 完全背包:动态规划 */
int unboundedKnapsackDP(int[] wgt, int[] val, int cap) {
int n = wgt.length;
// 初始化 dp 表
int[][] dp = new int[n + 1][cap + 1];
// 状态转移
for (int i = 1; i <= n; i++) {
for (int c = 1; c <= cap; c++) {
if (wgt[i - 1] > c) {
// 若超过背包容量,则不选物品 i
dp[i][c] = dp[i - 1][c];
} else {
// 不选和选物品 i 这两种方案的较大值
dp[i][c] = Math.max(dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1]);
}
}
}
return dp[n][cap];
}
/* 完全背包:动态规划 */
int UnboundedKnapsackDP(int[] wgt, int[] val, int cap) {
int n = wgt.Length;
// 初始化 dp 表
int[,] dp = new int[n + 1, cap + 1];
// 状态转移
for (int i = 1; i <= n; i++) {
for (int c = 1; c <= cap; c++) {
if (wgt[i - 1] > c) {
// 若超过背包容量,则不选物品 i
dp[i, c] = dp[i - 1, c];
} else {
// 不选和选物品 i 这两种方案的较大值
dp[i, c] = Math.Max(dp[i - 1, c], dp[i, c - wgt[i - 1]] + val[i - 1]);
}
}
}
return dp[n, cap];
}
/* 完全背包:动态规划 */
func unboundedKnapsackDP(wgt, val []int, cap int) int {
n := len(wgt)
// 初始化 dp 表
dp := make([][]int, n+1)
for i := 0; i <= n; i++ {
dp[i] = make([]int, cap+1)
}
// 状态转移
for i := 1; i <= n; i++ {
for c := 1; c <= cap; c++ {
if wgt[i-1] > c {
// 若超过背包容量,则不选物品 i
dp[i][c] = dp[i-1][c]
} else {
// 不选和选物品 i 这两种方案的较大值
dp[i][c] = int(math.Max(float64(dp[i-1][c]), float64(dp[i][c-wgt[i-1]]+val[i-1])))
}
}
}
return dp[n][cap]
}
/* 完全背包:动态规划 */
func unboundedKnapsackDP(wgt: [Int], val: [Int], cap: Int) -> Int {
let n = wgt.count
// 初始化 dp 表
var dp = Array(repeating: Array(repeating: 0, count: cap + 1), count: n + 1)
// 状态转移
for i in 1 ... n {
for c in 1 ... cap {
if wgt[i - 1] > c {
// 若超过背包容量,则不选物品 i
dp[i][c] = dp[i - 1][c]
} else {
// 不选和选物品 i 这两种方案的较大值
dp[i][c] = max(dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1])
}
}
}
return dp[n][cap]
}
/* 完全背包:动态规划 */
function unboundedKnapsackDP(wgt, val, cap) {
const n = wgt.length;
// 初始化 dp 表
const dp = Array.from({ length: n + 1 }, () =>
Array.from({ length: cap + 1 }, () => 0)
);
// 状态转移
for (let i = 1; i <= n; i++) {
for (let c = 1; c <= cap; c++) {
if (wgt[i - 1] > c) {
// 若超过背包容量,则不选物品 i
dp[i][c] = dp[i - 1][c];
} else {
// 不选和选物品 i 这两种方案的较大值
dp[i][c] = Math.max(
dp[i - 1][c],
dp[i][c - wgt[i - 1]] + val[i - 1]
);
}
}
}
return dp[n][cap];
}
/* 完全背包:动态规划 */
function unboundedKnapsackDP(
wgt: Array<number>,
val: Array<number>,
cap: number
): number {
const n = wgt.length;
// 初始化 dp 表
const dp = Array.from({ length: n + 1 }, () =>
Array.from({ length: cap + 1 }, () => 0)
);
// 状态转移
for (let i = 1; i <= n; i++) {
for (let c = 1; c <= cap; c++) {
if (wgt[i - 1] > c) {
// 若超过背包容量,则不选物品 i
dp[i][c] = dp[i - 1][c];
} else {
// 不选和选物品 i 这两种方案的较大值
dp[i][c] = Math.max(
dp[i - 1][c],
dp[i][c - wgt[i - 1]] + val[i - 1]
);
}
}
}
return dp[n][cap];
}
/* 完全背包:动态规划 */
int unboundedKnapsackDP(List<int> wgt, List<int> val, int cap) {
int n = wgt.length;
// 初始化 dp 表
List<List<int>> dp = List.generate(n + 1, (index) => List.filled(cap + 1, 0));
// 状态转移
for (int i = 1; i <= n; i++) {
for (int c = 1; c <= cap; c++) {
if (wgt[i - 1] > c) {
// 若超过背包容量,则不选物品 i
dp[i][c] = dp[i - 1][c];
} else {
// 不选和选物品 i 这两种方案的较大值
dp[i][c] = max(dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1]);
}
}
}
return dp[n][cap];
}
/* 完全背包:动态规划 */
fn unbounded_knapsack_dp(wgt: &[i32], val: &[i32], cap: usize) -> i32 {
let n = wgt.len();
// 初始化 dp 表
let mut dp = vec![vec![0; cap + 1]; n + 1];
// 状态转移
for i in 1..=n {
for c in 1..=cap {
if wgt[i - 1] > c as i32 {
// 若超过背包容量,则不选物品 i
dp[i][c] = dp[i - 1][c];
} else {
// 不选和选物品 i 这两种方案的较大值
dp[i][c] = std::cmp::max(dp[i - 1][c], dp[i][c - wgt[i - 1] as usize] + val[i - 1]);
}
}
}
return dp[n][cap];
}
/* 完全背包:动态规划 */
int unboundedKnapsackDP(int wgt[], int val[], int cap, int wgtSize) {
int n = wgtSize;
// 初始化 dp 表
int **dp = malloc((n + 1) * sizeof(int *));
for (int i = 0; i <= n; i++) {
dp[i] = calloc(cap + 1, sizeof(int));
}
// 状态转移
for (int i = 1; i <= n; i++) {
for (int c = 1; c <= cap; c++) {
if (wgt[i - 1] > c) {
// 若超过背包容量,则不选物品 i
dp[i][c] = dp[i - 1][c];
} else {
// 不选和选物品 i 这两种方案的较大值
dp[i][c] = myMax(dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1]);
}
}
}
int res = dp[n][cap];
// 释放内存
for (int i = 0; i <= n; i++) {
free(dp[i]);
}
return res;
}
/* 完全背包:动态规划 */
fun unboundedKnapsackDP(wgt: IntArray, _val: IntArray, cap: Int): Int {
val n = wgt.size
// 初始化 dp 表
val dp = Array(n + 1) { IntArray(cap + 1) }
// 状态转移
for (i in 1..n) {
for (c in 1..cap) {
if (wgt[i - 1] > c) {
// 若超过背包容量,则不选物品 i
dp[i][c] = dp[i - 1][c]
} else {
// 不选和选物品 i 这两种方案的较大值
dp[i][c] = max(dp[i - 1][c], dp[i][c - wgt[i - 1]] + _val[i - 1])
}
}
}
return dp[n][cap]
}
### 完全背包:动态规划 ###
def unbounded_knapsack_dp(wgt, val, cap)
n = wgt.length
# 初始化 dp 表
dp = Array.new(n + 1) { Array.new(cap + 1, 0) }
# 状态转移
for i in 1...(n + 1)
for c in 1...(cap + 1)
if wgt[i - 1] > c
# 若超过背包容量,则不选物品 i
dp[i][c] = dp[i - 1][c]
else
# 不选和选物品 i 这两种方案的较大值
dp[i][c] = [dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1]].max
end
end
end
dp[n][cap]
end
可视化运行
3. 空间优化¶
由于当前状态是从左边和上边的状态转移而来的,因此空间优化后应该对 \(dp\) 表中的每一行进行正序遍历。
这个遍历顺序与 0-1 背包正好相反。请借助图 14-23 来理解两者的区别。
图 14-23 完全背包问题在空间优化后的动态规划过程
图解 14-23:完全背包的单行更新
按容量从小到大正序更新单行数组,复用本轮较小容量的新解,使同种物品可以重复选取。
背包容量上限为 4,三种物品均可重复选取,具体重量和价值见下方“完全背包正序更新的物品输入”表。本例从第 1 种物品苹果已处理完毕开始,只演示第 2 种物品菠萝这一轮,第 3 种物品西瓜尚未参与。
二维状态 dp[i, c] 表示仅用前 i 种物品、总重量不超过容量 c 时的最大价值;空间优化后的单行数组 dp[c](容量索引 c 从 0 至 4)按轮依次覆盖上一轮结果。
第 i = 2 轮按容量 c = 1、2、3、4 正序遍历。容量不足以放入菠萝(c < 2)时沿用上一轮旧值;装得下时(c >= 2),比较不选菠萝的旧值 dp[c] 与选入菠萝的本轮值 dp[c - 2] + 11,取较大者写入 dp[c]。较小正容量在本轮已先处理,容量 0 始终保持有效边界 0,因此正序读取本行左侧的 dp[c - 2] 可以再次选入菠萝,实现同种物品重复选取;0-1 背包每件限用一次、必须倒序读取上一轮旧值的限制不适用于这里。
画面上方是二维表,下方是单行数组;图解按单行表、二维对照表的顺序提供每步完整状态,两表名称均含步号。单行表把数值与所属轮次分列:i = 1 表示仅苹果可选,i = 2 表示苹果、菠萝可选,不表示方案一定同时选入两者。蓝色表示上一轮状态,绿色表示本轮已处理;收尾时本轮结果统一改蓝,准备作为下一轮的旧状态。二维表中“未计算初值”0 不能当作已算出的解。
| 编号i | 物品 | 重量 | 价值 |
|---|---|---|---|
| 1 | 苹果 | 1 | 5 |
| 2 | 菠萝 | 2 | 11 |
| 3 | 西瓜 | 3 | 15 |
遍历 i = 2 前:单行保存 i = 1 的解
开始第 i = 2 轮(菠萝)之前,第 1 轮(仅苹果可选)已计算完毕:由于苹果可重复选取,容量 0 至 4 依次放入 0 至 4 个苹果,最大价值为 [0, 5, 10, 15, 20]。单行数组 dp 当前保存这组 i = 1 的解,准备从左到右正序处理第 2 种物品菠萝。
完全背包第 1 步:遍历 i = 2 前:单行保存 i = 1 的解——单行 dp:各容量的值与所属轮次 容量 c 当前值 所属轮次及可选范围 0 0 各轮共享的容量 0 边界 1 5 上一轮 i=1,仅苹果可选,尚未覆盖 2 10 上一轮 i=1,仅苹果可选,尚未覆盖 3 15 上一轮 i=1,仅苹果可选,尚未覆盖 4 20 上一轮 i=1,仅苹果可选,尚未覆盖 完全背包第 1 步:遍历 i = 2 前:单行保存 i = 1 的解——二维对照表:各子问题的计算进度 可选物品 容量0 容量1 容量2 容量3 容量4 前0种物品 0,边界有效 0,边界有效 0,边界有效 0,边界有效 0,边界有效 前1种物品 0,边界有效 5,已计算 10,已计算 15,已计算 20,已计算 前2种物品 0,边界有效 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 前3种物品 0,边界有效 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 正序处理容量 c = 1:装不下菠萝,保持 5
从容量 c = 1 开始正序遍历:菠萝重量 2 大于容量 1,无法放入菠萝。二维对照表中 dp[2, 1] 直接继承正上方 dp[1, 1] = 5;单行数组的 dp[1] 数值保持 5,但所属轮次已更新为本轮 i = 2(图中以绿色标示本轮已处理),而容量 2 至 4 仍为上一轮 i = 1 的旧值。
完全背包第 2 步:正序处理容量 c = 1:装不下菠萝,保持 5——单行 dp:各容量的值与所属轮次 容量 c 当前值 所属轮次及可选范围 0 0 各轮共享的容量 0 边界 1 5 本轮 i=2,可选范围:苹果、菠萝 2 10 上一轮 i=1,仅苹果可选,尚未覆盖 3 15 上一轮 i=1,仅苹果可选,尚未覆盖 4 20 上一轮 i=1,仅苹果可选,尚未覆盖 完全背包第 2 步:正序处理容量 c = 1:装不下菠萝,保持 5——二维对照表:各子问题的计算进度 可选物品 容量0 容量1 容量2 容量3 容量4 前0种物品 0,边界有效 0,边界有效 0,边界有效 0,边界有效 0,边界有效 前1种物品 0,边界有效 5,已计算 10,已计算 15,已计算 20,已计算 前2种物品 0,边界有效 5,已计算 0,未计算初值 0,未计算初值 0,未计算初值 前3种物品 0,边界有效 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 正序更新容量 c = 2:选入 1 个菠萝,更新为 11
向右正序推进到容量 c = 2:不选菠萝时沿用上一轮旧值 dp[2] = 10(两个苹果);选入 1 个菠萝时,读取本行左侧容量 0 的边界状态 dp[0] = 0 并加菠萝价值 11,得 11。取 max(10, 11) = 11,将单行 dp[2] 更新为本轮新值 11。
完全背包第 3 步:正序更新容量 c = 2:选入 1 个菠萝,更新为 11——单行 dp:各容量的值与所属轮次 容量 c 当前值 所属轮次及可选范围 0 0 各轮共享的容量 0 边界 1 5 本轮 i=2,可选范围:苹果、菠萝 2 11 本轮 i=2,可选范围:苹果、菠萝 3 15 上一轮 i=1,仅苹果可选,尚未覆盖 4 20 上一轮 i=1,仅苹果可选,尚未覆盖 完全背包第 3 步:正序更新容量 c = 2:选入 1 个菠萝,更新为 11——二维对照表:各子问题的计算进度 可选物品 容量0 容量1 容量2 容量3 容量4 前0种物品 0,边界有效 0,边界有效 0,边界有效 0,边界有效 0,边界有效 前1种物品 0,边界有效 5,已计算 10,已计算 15,已计算 20,已计算 前2种物品 0,边界有效 5,已计算 11,已计算 0,未计算初值 0,未计算初值 前3种物品 0,边界有效 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 正序更新容量 c = 3:苹果加菠萝,更新为 16
继续正序推进到容量 c = 3:不选菠萝时为上一轮旧值 dp[3] = 15(三个苹果);选入 1 个菠萝时,读取本行左侧已在本轮处理过的 dp[1] = 5(一个苹果),加上菠萝价值 11 得 16(一个苹果加一个菠萝)。取 max(15, 16) = 16,将 dp[3] 更新为 16。
完全背包第 4 步:正序更新容量 c = 3:苹果加菠萝,更新为 16——单行 dp:各容量的值与所属轮次 容量 c 当前值 所属轮次及可选范围 0 0 各轮共享的容量 0 边界 1 5 本轮 i=2,可选范围:苹果、菠萝 2 11 本轮 i=2,可选范围:苹果、菠萝 3 16 本轮 i=2,可选范围:苹果、菠萝 4 20 上一轮 i=1,仅苹果可选,尚未覆盖 完全背包第 4 步:正序更新容量 c = 3:苹果加菠萝,更新为 16——二维对照表:各子问题的计算进度 可选物品 容量0 容量1 容量2 容量3 容量4 前0种物品 0,边界有效 0,边界有效 0,边界有效 0,边界有效 0,边界有效 前1种物品 0,边界有效 5,已计算 10,已计算 15,已计算 20,已计算 前2种物品 0,边界有效 5,已计算 11,已计算 16,已计算 0,未计算初值 前3种物品 0,边界有效 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 正序更新容量 c = 4:复用本轮新值,重复选菠萝得 22
正序推进到容量 c = 4:不选菠萝时为上一轮旧值 dp[4] = 20(四个苹果);选入菠萝时,从本行左侧读取本轮刚更新过的 dp[2] = 11(已含 1 个菠萝),再加 1 个菠萝的价值 11 得到 22(共两个菠萝)。取 max(20, 22) = 22 写入 dp[4],直接体现正序遍历允许复用本轮新解、重复选取同一种物品。
完全背包第 5 步:正序更新容量 c = 4:复用本轮新值,重复选菠萝得 22——单行 dp:各容量的值与所属轮次 容量 c 当前值 所属轮次及可选范围 0 0 各轮共享的容量 0 边界 1 5 本轮 i=2,可选范围:苹果、菠萝 2 11 本轮 i=2,可选范围:苹果、菠萝 3 16 本轮 i=2,可选范围:苹果、菠萝 4 22 本轮 i=2,可选范围:苹果、菠萝 完全背包第 5 步:正序更新容量 c = 4:复用本轮新值,重复选菠萝得 22——二维对照表:各子问题的计算进度 可选物品 容量0 容量1 容量2 容量3 容量4 前0种物品 0,边界有效 0,边界有效 0,边界有效 0,边界有效 0,边界有效 前1种物品 0,边界有效 5,已计算 10,已计算 15,已计算 20,已计算 前2种物品 0,边界有效 5,已计算 11,已计算 16,已计算 22,已计算 前3种物品 0,边界有效 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 完成 i = 2 轮遍历:单行保存前两种物品的解
第 i = 2 轮正序遍历完成,单行 dp = [0, 5, 11, 16, 22] 保存前两种物品可选时容量 0 至 4 的最大价值。本步不再改写数值,只将本轮结果统一改为蓝色,作为下一轮的旧状态。二维对照表“前3种物品”行在容量 1 至 4 的 0 仍为未计算初值,容量 0 保持边界值 0;西瓜尚未开始处理。
完全背包第 6 步:完成 i = 2 轮遍历:单行保存前两种物品的解——单行 dp:各容量的值与所属轮次 容量 c 当前值 所属轮次及可选范围 0 0 各轮共享的容量 0 边界 1 5 本轮 i=2,可选范围:苹果、菠萝;将作为下一轮旧状态 2 11 本轮 i=2,可选范围:苹果、菠萝;将作为下一轮旧状态 3 16 本轮 i=2,可选范围:苹果、菠萝;将作为下一轮旧状态 4 22 本轮 i=2,可选范围:苹果、菠萝;将作为下一轮旧状态 完全背包第 6 步:完成 i = 2 轮遍历:单行保存前两种物品的解——二维对照表:各子问题的计算进度 可选物品 容量0 容量1 容量2 容量3 容量4 前0种物品 0,边界有效 0,边界有效 0,边界有效 0,边界有效 0,边界有效 前1种物品 0,边界有效 5,已计算 10,已计算 15,已计算 20,已计算 前2种物品 0,边界有效 5,已计算 11,已计算 16,已计算 22,已计算 前3种物品 0,边界有效 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值
按本例输入补充对照:若误用倒序,容量 4 会先于容量 2 处理,只能读取旧值 dp[2] = 10,得到 max(20, 10 + 11) = 21,错过两个菠萝的 22。这是从本例初始数组推算的反例,未画在图中;它说明完全背包为何需要正序复用本轮新值。
代码实现比较简单,仅需将数组 dp 的第一维删除:
def unbounded_knapsack_dp_comp(wgt: list[int], val: list[int], cap: int) -> int:
"""完全背包:空间优化后的动态规划"""
n = len(wgt)
# 初始化 dp 表
dp = [0] * (cap + 1)
# 状态转移
for i in range(1, n + 1):
# 正序遍历
for c in range(1, cap + 1):
if wgt[i - 1] > c:
# 若超过背包容量,则不选物品 i
dp[c] = dp[c]
else:
# 不选和选物品 i 这两种方案的较大值
dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1])
return dp[cap]
/* 完全背包:空间优化后的动态规划 */
int unboundedKnapsackDPComp(vector<int> &wgt, vector<int> &val, int cap) {
int n = wgt.size();
// 初始化 dp 表
vector<int> dp(cap + 1, 0);
// 状态转移
for (int i = 1; i <= n; i++) {
for (int c = 1; c <= cap; c++) {
if (wgt[i - 1] > c) {
// 若超过背包容量,则不选物品 i
dp[c] = dp[c];
} else {
// 不选和选物品 i 这两种方案的较大值
dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
}
}
}
return dp[cap];
}
/* 完全背包:空间优化后的动态规划 */
int unboundedKnapsackDPComp(int[] wgt, int[] val, int cap) {
int n = wgt.length;
// 初始化 dp 表
int[] dp = new int[cap + 1];
// 状态转移
for (int i = 1; i <= n; i++) {
for (int c = 1; c <= cap; c++) {
if (wgt[i - 1] > c) {
// 若超过背包容量,则不选物品 i
dp[c] = dp[c];
} else {
// 不选和选物品 i 这两种方案的较大值
dp[c] = Math.max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
}
}
}
return dp[cap];
}
/* 完全背包:空间优化后的动态规划 */
int UnboundedKnapsackDPComp(int[] wgt, int[] val, int cap) {
int n = wgt.Length;
// 初始化 dp 表
int[] dp = new int[cap + 1];
// 状态转移
for (int i = 1; i <= n; i++) {
for (int c = 1; c <= cap; c++) {
if (wgt[i - 1] > c) {
// 若超过背包容量,则不选物品 i
dp[c] = dp[c];
} else {
// 不选和选物品 i 这两种方案的较大值
dp[c] = Math.Max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
}
}
}
return dp[cap];
}
/* 完全背包:空间优化后的动态规划 */
func unboundedKnapsackDPComp(wgt, val []int, cap int) int {
n := len(wgt)
// 初始化 dp 表
dp := make([]int, cap+1)
// 状态转移
for i := 1; i <= n; i++ {
for c := 1; c <= cap; c++ {
if wgt[i-1] > c {
// 若超过背包容量,则不选物品 i
dp[c] = dp[c]
} else {
// 不选和选物品 i 这两种方案的较大值
dp[c] = int(math.Max(float64(dp[c]), float64(dp[c-wgt[i-1]]+val[i-1])))
}
}
}
return dp[cap]
}
/* 完全背包:空间优化后的动态规划 */
func unboundedKnapsackDPComp(wgt: [Int], val: [Int], cap: Int) -> Int {
let n = wgt.count
// 初始化 dp 表
var dp = Array(repeating: 0, count: cap + 1)
// 状态转移
for i in 1 ... n {
for c in 1 ... cap {
if wgt[i - 1] > c {
// 若超过背包容量,则不选物品 i
dp[c] = dp[c]
} else {
// 不选和选物品 i 这两种方案的较大值
dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1])
}
}
}
return dp[cap]
}
/* 完全背包:空间优化后的动态规划 */
function unboundedKnapsackDPComp(wgt, val, cap) {
const n = wgt.length;
// 初始化 dp 表
const dp = Array.from({ length: cap + 1 }, () => 0);
// 状态转移
for (let i = 1; i <= n; i++) {
for (let c = 1; c <= cap; c++) {
if (wgt[i - 1] > c) {
// 若超过背包容量,则不选物品 i
dp[c] = dp[c];
} else {
// 不选和选物品 i 这两种方案的较大值
dp[c] = Math.max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
}
}
}
return dp[cap];
}
/* 完全背包:空间优化后的动态规划 */
function unboundedKnapsackDPComp(
wgt: Array<number>,
val: Array<number>,
cap: number
): number {
const n = wgt.length;
// 初始化 dp 表
const dp = Array.from({ length: cap + 1 }, () => 0);
// 状态转移
for (let i = 1; i <= n; i++) {
for (let c = 1; c <= cap; c++) {
if (wgt[i - 1] > c) {
// 若超过背包容量,则不选物品 i
dp[c] = dp[c];
} else {
// 不选和选物品 i 这两种方案的较大值
dp[c] = Math.max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
}
}
}
return dp[cap];
}
/* 完全背包:空间优化后的动态规划 */
int unboundedKnapsackDPComp(List<int> wgt, List<int> val, int cap) {
int n = wgt.length;
// 初始化 dp 表
List<int> dp = List.filled(cap + 1, 0);
// 状态转移
for (int i = 1; i <= n; i++) {
for (int c = 1; c <= cap; c++) {
if (wgt[i - 1] > c) {
// 若超过背包容量,则不选物品 i
dp[c] = dp[c];
} else {
// 不选和选物品 i 这两种方案的较大值
dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
}
}
}
return dp[cap];
}
/* 完全背包:空间优化后的动态规划 */
fn unbounded_knapsack_dp_comp(wgt: &[i32], val: &[i32], cap: usize) -> i32 {
let n = wgt.len();
// 初始化 dp 表
let mut dp = vec![0; cap + 1];
// 状态转移
for i in 1..=n {
for c in 1..=cap {
if wgt[i - 1] > c as i32 {
// 若超过背包容量,则不选物品 i
dp[c] = dp[c];
} else {
// 不选和选物品 i 这两种方案的较大值
dp[c] = std::cmp::max(dp[c], dp[c - wgt[i - 1] as usize] + val[i - 1]);
}
}
}
dp[cap]
}
/* 完全背包:空间优化后的动态规划 */
int unboundedKnapsackDPComp(int wgt[], int val[], int cap, int wgtSize) {
int n = wgtSize;
// 初始化 dp 表
int *dp = calloc(cap + 1, sizeof(int));
// 状态转移
for (int i = 1; i <= n; i++) {
for (int c = 1; c <= cap; c++) {
if (wgt[i - 1] > c) {
// 若超过背包容量,则不选物品 i
dp[c] = dp[c];
} else {
// 不选和选物品 i 这两种方案的较大值
dp[c] = myMax(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
}
}
}
int res = dp[cap];
// 释放内存
free(dp);
return res;
}
/* 完全背包:空间优化后的动态规划 */
fun unboundedKnapsackDPComp(
wgt: IntArray,
_val: IntArray,
cap: Int
): Int {
val n = wgt.size
// 初始化 dp 表
val dp = IntArray(cap + 1)
// 状态转移
for (i in 1..n) {
for (c in 1..cap) {
if (wgt[i - 1] > c) {
// 若超过背包容量,则不选物品 i
dp[c] = dp[c]
} else {
// 不选和选物品 i 这两种方案的较大值
dp[c] = max(dp[c], dp[c - wgt[i - 1]] + _val[i - 1])
}
}
}
return dp[cap]
}
### 完全背包:空间优化后的动态规划 ###
def unbounded_knapsack_dp_comp(wgt, val, cap)
n = wgt.length
# 初始化 dp 表
dp = Array.new(cap + 1, 0)
# 状态转移
for i in 1...(n + 1)
# 正序遍历
for c in 1...(cap + 1)
if wgt[i -1] > c
# 若超过背包容量,则不选物品 i
dp[c] = dp[c]
else
# 不选和选物品 i 这两种方案的较大值
dp[c] = [dp[c], dp[c - wgt[i - 1]] + val[i - 1]].max
end
end
end
dp[cap]
end
可视化运行
14.5.2 零钱兑换问题¶
背包问题是一大类动态规划问题的代表,其拥有很多变种,例如零钱兑换问题。
Question
给定 \(n\) 种硬币,第 \(i\) 种硬币的面值为 \(coins[i - 1]\) ,目标金额为 \(amt\) ,每种硬币可以重复选取,问能够凑出目标金额的最少硬币数量。如果无法凑出目标金额,则返回 \(-1\) 。示例如图 14-24 所示。
图 14-24 零钱兑换问题的示例数据
图解 14-24:零钱兑换的最少硬币数
图示一种凑出金额 11 的最优选币方案。
零钱兑换问题给定 3 种硬币面值 coins = [1, 2, 5],每种面值的硬币数量无限;本示例的目标金额为 amt = 11(注意与后续零钱兑换 II 示例的目标金额 5、以及动态规划填表图的目标金额 4 区分)。任务是求恰好凑出目标金额 11 所需的最少硬币数量。
画面左侧表格列出编号 i 与面值 coins[i-1];面值 1 所在行以浅橙色、面值 5 所在行以浅绿色突出,两条箭头分别标注选 1 枚和选 2 枚,汇入右侧标有“目标金额 amt = 11”的钱袋。面值 2 未选用。下表把这些高亮及箭头关系整理为选用枚数。
图底给出“最优硬币组合:1 + 5 + 5”和“最少硬币数量:3”。
| 编号i | 面值 | 图中方案选用枚数 |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 2 | 0 |
| 3 | 5 | 2 |
按图中组合计算,1 + 5 + 5 = 11,共用 3 枚。补充最少性的理由:最大面值为 5,任意两枚的总额至多为 5 + 5 = 10,小于 11,因此少于 3 枚无法完成;这一论证由输入数据推得,未写在原图中。
1. 动态规划思路¶
零钱兑换可以看作完全背包问题的一种特殊情况,两者具有以下联系与不同点。
- 两道题可以相互转换,“物品”对应“硬币”、“物品重量”对应“硬币面值”、“背包容量”对应“目标金额”。
- 优化目标相反,完全背包问题是要最大化物品价值,零钱兑换问题是要最小化硬币数量。
- 完全背包问题是求“不超过”背包容量下的解,零钱兑换是求“恰好”凑到目标金额的解。
第一步:思考每轮的决策,定义状态,从而得到 \(dp\) 表
状态 \([i, a]\) 对应的子问题为:前 \(i\) 种硬币能够凑出金额 \(a\) 的最少硬币数量,记为 \(dp[i, a]\) 。
二维 \(dp\) 表的尺寸为 \((n+1) \times (amt+1)\) 。
第二步:找出最优子结构,进而推导出状态转移方程
本题与完全背包问题的状态转移方程存在以下两点差异。
- 本题要求最小值,因此需将运算符 \(\max()\) 更改为 \(\min()\) 。
- 优化主体是硬币数量而非商品价值,因此在选中硬币时执行 \(+1\) 即可。
第三步:确定边界条件和状态转移顺序
当目标金额为 \(0\) 时,凑出它的最少硬币数量为 \(0\) ,即首列所有 \(dp[i, 0]\) 都等于 \(0\) 。
当无硬币时,无法凑出任意 \(> 0\) 的目标金额,即是无效解。为使状态转移方程中的 \(\min()\) 函数能够识别并过滤无效解,我们考虑使用 \(+ \infty\) 来表示它们,即令首行所有 \(dp[0, a]\) 都等于 \(+ \infty\) 。
2. 代码实现¶
大多数编程语言并未提供 \(+ \infty\) 变量,只能使用整型 int 的最大值来代替。而这又会导致大数越界:状态转移方程中的 \(+ 1\) 操作可能发生溢出。
为此,我们采用数字 \(amt + 1\) 来表示无效解,因为凑出 \(amt\) 的硬币数量最多为 \(amt\) 。最后返回前,判断 \(dp[n, amt]\) 是否等于 \(amt + 1\) ,若是则返回 \(-1\) ,代表无法凑出目标金额。代码如下所示:
def coin_change_dp(coins: list[int], amt: int) -> int:
"""零钱兑换:动态规划"""
n = len(coins)
MAX = amt + 1
# 初始化 dp 表
dp = [[0] * (amt + 1) for _ in range(n + 1)]
# 状态转移:首行首列
for a in range(1, amt + 1):
dp[0][a] = MAX
# 状态转移:其余行和列
for i in range(1, n + 1):
for a in range(1, amt + 1):
if coins[i - 1] > a:
# 若超过目标金额,则不选硬币 i
dp[i][a] = dp[i - 1][a]
else:
# 不选和选硬币 i 这两种方案的较小值
dp[i][a] = min(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1)
return dp[n][amt] if dp[n][amt] != MAX else -1
/* 零钱兑换:动态规划 */
int coinChangeDP(vector<int> &coins, int amt) {
int n = coins.size();
int MAX = amt + 1;
// 初始化 dp 表
vector<vector<int>> dp(n + 1, vector<int>(amt + 1, 0));
// 状态转移:首行首列
for (int a = 1; a <= amt; a++) {
dp[0][a] = MAX;
}
// 状态转移:其余行和列
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超过目标金额,则不选硬币 i
dp[i][a] = dp[i - 1][a];
} else {
// 不选和选硬币 i 这两种方案的较小值
dp[i][a] = min(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1);
}
}
}
return dp[n][amt] != MAX ? dp[n][amt] : -1;
}
/* 零钱兑换:动态规划 */
int coinChangeDP(int[] coins, int amt) {
int n = coins.length;
int MAX = amt + 1;
// 初始化 dp 表
int[][] dp = new int[n + 1][amt + 1];
// 状态转移:首行首列
for (int a = 1; a <= amt; a++) {
dp[0][a] = MAX;
}
// 状态转移:其余行和列
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超过目标金额,则不选硬币 i
dp[i][a] = dp[i - 1][a];
} else {
// 不选和选硬币 i 这两种方案的较小值
dp[i][a] = Math.min(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1);
}
}
}
return dp[n][amt] != MAX ? dp[n][amt] : -1;
}
/* 零钱兑换:动态规划 */
int CoinChangeDP(int[] coins, int amt) {
int n = coins.Length;
int MAX = amt + 1;
// 初始化 dp 表
int[,] dp = new int[n + 1, amt + 1];
// 状态转移:首行首列
for (int a = 1; a <= amt; a++) {
dp[0, a] = MAX;
}
// 状态转移:其余行和列
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超过目标金额,则不选硬币 i
dp[i, a] = dp[i - 1, a];
} else {
// 不选和选硬币 i 这两种方案的较小值
dp[i, a] = Math.Min(dp[i - 1, a], dp[i, a - coins[i - 1]] + 1);
}
}
}
return dp[n, amt] != MAX ? dp[n, amt] : -1;
}
/* 零钱兑换:动态规划 */
func coinChangeDP(coins []int, amt int) int {
n := len(coins)
max := amt + 1
// 初始化 dp 表
dp := make([][]int, n+1)
for i := 0; i <= n; i++ {
dp[i] = make([]int, amt+1)
}
// 状态转移:首行首列
for a := 1; a <= amt; a++ {
dp[0][a] = max
}
// 状态转移:其余行和列
for i := 1; i <= n; i++ {
for a := 1; a <= amt; a++ {
if coins[i-1] > a {
// 若超过目标金额,则不选硬币 i
dp[i][a] = dp[i-1][a]
} else {
// 不选和选硬币 i 这两种方案的较小值
dp[i][a] = int(math.Min(float64(dp[i-1][a]), float64(dp[i][a-coins[i-1]]+1)))
}
}
}
if dp[n][amt] != max {
return dp[n][amt]
}
return -1
}
/* 零钱兑换:动态规划 */
func coinChangeDP(coins: [Int], amt: Int) -> Int {
let n = coins.count
let MAX = amt + 1
// 初始化 dp 表
var dp = Array(repeating: Array(repeating: 0, count: amt + 1), count: n + 1)
// 状态转移:首行首列
for a in 1 ... amt {
dp[0][a] = MAX
}
// 状态转移:其余行和列
for i in 1 ... n {
for a in 1 ... amt {
if coins[i - 1] > a {
// 若超过目标金额,则不选硬币 i
dp[i][a] = dp[i - 1][a]
} else {
// 不选和选硬币 i 这两种方案的较小值
dp[i][a] = min(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1)
}
}
}
return dp[n][amt] != MAX ? dp[n][amt] : -1
}
/* 零钱兑换:动态规划 */
function coinChangeDP(coins, amt) {
const n = coins.length;
const MAX = amt + 1;
// 初始化 dp 表
const dp = Array.from({ length: n + 1 }, () =>
Array.from({ length: amt + 1 }, () => 0)
);
// 状态转移:首行首列
for (let a = 1; a <= amt; a++) {
dp[0][a] = MAX;
}
// 状态转移:其余行和列
for (let i = 1; i <= n; i++) {
for (let a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超过目标金额,则不选硬币 i
dp[i][a] = dp[i - 1][a];
} else {
// 不选和选硬币 i 这两种方案的较小值
dp[i][a] = Math.min(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1);
}
}
}
return dp[n][amt] !== MAX ? dp[n][amt] : -1;
}
/* 零钱兑换:动态规划 */
function coinChangeDP(coins: Array<number>, amt: number): number {
const n = coins.length;
const MAX = amt + 1;
// 初始化 dp 表
const dp = Array.from({ length: n + 1 }, () =>
Array.from({ length: amt + 1 }, () => 0)
);
// 状态转移:首行首列
for (let a = 1; a <= amt; a++) {
dp[0][a] = MAX;
}
// 状态转移:其余行和列
for (let i = 1; i <= n; i++) {
for (let a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超过目标金额,则不选硬币 i
dp[i][a] = dp[i - 1][a];
} else {
// 不选和选硬币 i 这两种方案的较小值
dp[i][a] = Math.min(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1);
}
}
}
return dp[n][amt] !== MAX ? dp[n][amt] : -1;
}
/* 零钱兑换:动态规划 */
int coinChangeDP(List<int> coins, int amt) {
int n = coins.length;
int MAX = amt + 1;
// 初始化 dp 表
List<List<int>> dp = List.generate(n + 1, (index) => List.filled(amt + 1, 0));
// 状态转移:首行首列
for (int a = 1; a <= amt; a++) {
dp[0][a] = MAX;
}
// 状态转移:其余行和列
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超过目标金额,则不选硬币 i
dp[i][a] = dp[i - 1][a];
} else {
// 不选和选硬币 i 这两种方案的较小值
dp[i][a] = min(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1);
}
}
}
return dp[n][amt] != MAX ? dp[n][amt] : -1;
}
/* 零钱兑换:动态规划 */
fn coin_change_dp(coins: &[i32], amt: usize) -> i32 {
let n = coins.len();
let max = amt + 1;
// 初始化 dp 表
let mut dp = vec![vec![0; amt + 1]; n + 1];
// 状态转移:首行首列
for a in 1..=amt {
dp[0][a] = max;
}
// 状态转移:其余行和列
for i in 1..=n {
for a in 1..=amt {
if coins[i - 1] > a as i32 {
// 若超过目标金额,则不选硬币 i
dp[i][a] = dp[i - 1][a];
} else {
// 不选和选硬币 i 这两种方案的较小值
dp[i][a] = std::cmp::min(dp[i - 1][a], dp[i][a - coins[i - 1] as usize] + 1);
}
}
}
if dp[n][amt] != max {
return dp[n][amt] as i32;
} else {
-1
}
}
/* 零钱兑换:动态规划 */
int coinChangeDP(int coins[], int amt, int coinsSize) {
int n = coinsSize;
int MAX = amt + 1;
// 初始化 dp 表
int **dp = malloc((n + 1) * sizeof(int *));
for (int i = 0; i <= n; i++) {
dp[i] = calloc(amt + 1, sizeof(int));
}
// 状态转移:首行首列
for (int a = 1; a <= amt; a++) {
dp[0][a] = MAX;
}
// 状态转移:其余行和列
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超过目标金额,则不选硬币 i
dp[i][a] = dp[i - 1][a];
} else {
// 不选和选硬币 i 这两种方案的较小值
dp[i][a] = myMin(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1);
}
}
}
int res = dp[n][amt] != MAX ? dp[n][amt] : -1;
// 释放内存
for (int i = 0; i <= n; i++) {
free(dp[i]);
}
free(dp);
return res;
}
/* 零钱兑换:动态规划 */
fun coinChangeDP(coins: IntArray, amt: Int): Int {
val n = coins.size
val MAX = amt + 1
// 初始化 dp 表
val dp = Array(n + 1) { IntArray(amt + 1) }
// 状态转移:首行首列
for (a in 1..amt) {
dp[0][a] = MAX
}
// 状态转移:其余行和列
for (i in 1..n) {
for (a in 1..amt) {
if (coins[i - 1] > a) {
// 若超过目标金额,则不选硬币 i
dp[i][a] = dp[i - 1][a]
} else {
// 不选和选硬币 i 这两种方案的较小值
dp[i][a] = min(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1)
}
}
}
return if (dp[n][amt] != MAX) dp[n][amt] else -1
}
### 零钱兑换:动态规划 ###
def coin_change_dp(coins, amt)
n = coins.length
_MAX = amt + 1
# 初始化 dp 表
dp = Array.new(n + 1) { Array.new(amt + 1, 0) }
# 状态转移:首行首列
(1...(amt + 1)).each { |a| dp[0][a] = _MAX }
# 状态转移:其余行和列
for i in 1...(n + 1)
for a in 1...(amt + 1)
if coins[i - 1] > a
# 若超过目标金额,则不选硬币 i
dp[i][a] = dp[i - 1][a]
else
# 不选和选硬币 i 这两种方案的较小值
dp[i][a] = [dp[i - 1][a], dp[i][a - coins[i - 1]] + 1].min
end
end
end
dp[n][amt] != _MAX ? dp[n][amt] : -1
end
可视化运行
图 14-25 展示了零钱兑换的动态规划过程,和完全背包问题非常相似。
图 14-25 零钱兑换问题的动态规划过程
图解 14-25:零钱兑换的动态规划
按硬币种类与目标金额逐格填表,求恰好凑出 4 元所需的最少硬币枚数。
可选硬币面值为 1、2、5 元(共 3 种,每种均可重复选取),目标金额为 4 元。状态 dp[i, a] 表示仅用前 i 种硬币恰好凑出金额 a 的最少硬币枚数;二维 dp 表共 4 行 5 列,行索引 i 从 0 至 3,列索引 a 从 0 至 4。
MAX = 目标金额 + 1 = 5 是表示“不可达(无解)”的边界标记,绝非需要 5 枚硬币。目标金额 0 不需要硬币,首列边界值为 0;无硬币可用(i = 0)时,任何正金额均不可达。
先创建 4×5 全零表,再将首行正金额格 dp[0, 1] 至 dp[0, 4] 设为不可达标记 MAX = 5,首列 dp[0, 0] 至 dp[3, 0] 保持有效边界 0。随后按行 i = 1 至 3、每行金额 a = 1 至 4 依次填表:当前硬币面值大于金额 a 时无法选入,直接继承正上方 dp[i - 1, a];否则比较上方 dp[i - 1, a](不选该硬币)与本行左方 dp[i, a - 面值] + 1(选入一枚该硬币),取较小值。从本行左方转移允许重复选取同种硬币。
每步保留一张完整 dp 状态表,表名含步号及本步动作,行头同时给出 i 与可用面值,列头给出金额。首列边界格标为“边界已设”,首行无解格标为“MAX,不可达边界”;此前步骤写入的格标为“已计算”;未计算格标为“未计算初值”,不能当作已求得的最少枚数。本步新算出的格标为“本步写入”,最后一步将右下角标为“返回值”;可在第 15 步表中查询全部最终值。
| 编号i | 面值 |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 5 |
创建 4×5 初始全零 dp 表
根据 3 种硬币(面值 1、2、5)与目标金额 4,创建 4×5 的二维 dp 表(行 i = 0 至 3,列 a = 0 至 4)。刚分配时所有单元格默认置为 0:首列金额 0 的 0 即为已设边界(凑出 0 元需 0 枚硬币),而其余正金额格的 0 均为尚未计算的初值,等待下一步设置首行 MAX 不可达边界。
零钱兑换第 1 步:创建全零表后的完整 dp 表(MAX=5,不可达) 前 i 种硬币及可用面值 金额0 金额1 金额2 金额3 金额4 i=0,无硬币 0,边界已设 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 i=1,面值 1 0,边界已设 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 i=2,面值 1、2 0,边界已设 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 i=3,面值 1、2、5 0,边界已设 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 设置首行正金额为不可达边界 MAX = 5
无硬币可用(i = 0)时无法凑出任何大于 0 的金额,因此将首行正金额格 dp[0, 1] 至 dp[0, 4] 设为不可达标记 MAX = 5(表示状态已定义为无解,而非需要 5 枚硬币);金额 a = 0 时最少需 0 枚硬币,首列 dp[0, 0] 至 dp[3, 0] 保持已设边界 0。第 1 至 3 行正金额格的 0 仍为未计算初值。
零钱兑换第 2 步:初始化边界后的完整 dp 表(MAX=5,不可达) 前 i 种硬币及可用面值 金额0 金额1 金额2 金额3 金额4 i=0,无硬币 0,边界已设 MAX,不可达边界 MAX,不可达边界 MAX,不可达边界 MAX,不可达边界 i=1,面值 1 0,边界已设 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 i=2,面值 1、2 0,边界已设 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 i=3,面值 1、2、5 0,边界已设 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 计算 dp[1, 1](面值 1、金额 1):最少 1 枚
开始处理第 1 种硬币(面值 1),计算金额 a = 1 的 dp[1, 1]:不选面值 1 硬币时取正上方 dp[0, 1] = MAX(5,不可达);选入 1 枚面值 1 硬币时取本行左方边界 dp[1, 0] = 0 加 1 得 1。取较小值 min(MAX, 1) = 1,写入 dp[1, 1] = 1。这对应 1 枚 1 元硬币。
零钱兑换第 3 步:计算 dp[1, 1]后的完整 dp 表(MAX=5,不可达) 前 i 种硬币及可用面值 金额0 金额1 金额2 金额3 金额4 i=0,无硬币 0,边界已设 MAX,不可达边界 MAX,不可达边界 MAX,不可达边界 MAX,不可达边界 i=1,面值 1 0,边界已设 1,本步写入 0,未计算初值 0,未计算初值 0,未计算初值 i=2,面值 1、2 0,边界已设 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 i=3,面值 1、2、5 0,边界已设 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 计算 dp[1, 2](面值 1、金额 2):最少 2 枚
继续用第 1 种硬币(面值 1)计算金额 a = 2 的 dp[1, 2]:不选时为正上方 dp[0, 2] = MAX(不可达);选入 1 枚面值 1 硬币时,复用本行左方刚算出的 dp[1, 1] = 1 再加 1 得 2(两枚 1 元)。取 min(MAX, 2) = 2,写入 dp[1, 2] = 2。
零钱兑换第 4 步:计算 dp[1, 2]后的完整 dp 表(MAX=5,不可达) 前 i 种硬币及可用面值 金额0 金额1 金额2 金额3 金额4 i=0,无硬币 0,边界已设 MAX,不可达边界 MAX,不可达边界 MAX,不可达边界 MAX,不可达边界 i=1,面值 1 0,边界已设 1,已计算 2,本步写入 0,未计算初值 0,未计算初值 i=2,面值 1、2 0,边界已设 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 i=3,面值 1、2、5 0,边界已设 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 计算 dp[1, 3](面值 1、金额 3):最少 3 枚
继续用第 1 种硬币(面值 1)计算金额 a = 3 的 dp[1, 3]:不选时为正上方 dp[0, 3] = MAX(不可达);选入 1 枚面值 1 硬币时由本行左方 dp[1, 2] = 2 加 1 得 3(三枚 1 元)。取 min(MAX, 3) = 3,写入 dp[1, 3] = 3。
零钱兑换第 5 步:计算 dp[1, 3]后的完整 dp 表(MAX=5,不可达) 前 i 种硬币及可用面值 金额0 金额1 金额2 金额3 金额4 i=0,无硬币 0,边界已设 MAX,不可达边界 MAX,不可达边界 MAX,不可达边界 MAX,不可达边界 i=1,面值 1 0,边界已设 1,已计算 2,已计算 3,本步写入 0,未计算初值 i=2,面值 1、2 0,边界已设 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 i=3,面值 1、2、5 0,边界已设 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 计算 dp[1, 4](面值 1、金额 4):最少 4 枚
继续用第 1 种硬币(面值 1)计算金额 a = 4 的 dp[1, 4]:不选时为正上方 dp[0, 4] = MAX(不可达);选入 1 枚面值 1 硬币时由本行左方 dp[1, 3] = 3 加 1 得 4(四枚 1 元)。取 min(MAX, 4) = 4 写入 dp[1, 4],第 1 行计算完毕。
零钱兑换第 6 步:计算 dp[1, 4]后的完整 dp 表(MAX=5,不可达) 前 i 种硬币及可用面值 金额0 金额1 金额2 金额3 金额4 i=0,无硬币 0,边界已设 MAX,不可达边界 MAX,不可达边界 MAX,不可达边界 MAX,不可达边界 i=1,面值 1 0,边界已设 1,已计算 2,已计算 3,已计算 4,本步写入 i=2,面值 1、2 0,边界已设 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 i=3,面值 1、2、5 0,边界已设 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 计算 dp[2, 1](面值 2、金额 1):面值过大,继承 1 枚
进入第 2 行,引入第 2 种硬币(面值 2),计算金额 a = 1 的 dp[2, 1]。由于硬币面值 2 大于当前金额 1,无法选入 2 元硬币,直接继承正上方 dp[1, 1] = 1,写入 dp[2, 1] = 1。
零钱兑换第 7 步:计算 dp[2, 1]后的完整 dp 表(MAX=5,不可达) 前 i 种硬币及可用面值 金额0 金额1 金额2 金额3 金额4 i=0,无硬币 0,边界已设 MAX,不可达边界 MAX,不可达边界 MAX,不可达边界 MAX,不可达边界 i=1,面值 1 0,边界已设 1,已计算 2,已计算 3,已计算 4,已计算 i=2,面值 1、2 0,边界已设 1,本步写入 0,未计算初值 0,未计算初值 0,未计算初值 i=3,面值 1、2、5 0,边界已设 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 计算 dp[2, 2](面值 2、金额 2):选 1 枚 2 元,写入 1
处理第 2 种硬币(面值 2)、金额 a = 2:不选 2 元硬币时继承正上方 dp[1, 2] = 2(两枚 1 元);选入 1 枚 2 元硬币时从本行左方边界 dp[2, 0] = 0 加 1 得 1(1 枚 2 元)。取较小值 min(2, 1) = 1,写入 dp[2, 2] = 1。
零钱兑换第 8 步:计算 dp[2, 2]后的完整 dp 表(MAX=5,不可达) 前 i 种硬币及可用面值 金额0 金额1 金额2 金额3 金额4 i=0,无硬币 0,边界已设 MAX,不可达边界 MAX,不可达边界 MAX,不可达边界 MAX,不可达边界 i=1,面值 1 0,边界已设 1,已计算 2,已计算 3,已计算 4,已计算 i=2,面值 1、2 0,边界已设 1,已计算 1,本步写入 0,未计算初值 0,未计算初值 i=3,面值 1、2、5 0,边界已设 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 计算 dp[2, 3](面值 2、金额 3):1 元加 2 元,写入 2 枚
处理第 2 种硬币(面值 2)、金额 a = 3:不选 2 元硬币时为正上方 dp[1, 3] = 3(三枚 1 元);选入 1 枚 2 元硬币时从本行左方 dp[2, 1] = 1(1 枚 1 元)加 1 得 2(1 元与 2 元各 1 枚)。取 min(3, 2) = 2,写入 dp[2, 3] = 2。
零钱兑换第 9 步:计算 dp[2, 3]后的完整 dp 表(MAX=5,不可达) 前 i 种硬币及可用面值 金额0 金额1 金额2 金额3 金额4 i=0,无硬币 0,边界已设 MAX,不可达边界 MAX,不可达边界 MAX,不可达边界 MAX,不可达边界 i=1,面值 1 0,边界已设 1,已计算 2,已计算 3,已计算 4,已计算 i=2,面值 1、2 0,边界已设 1,已计算 1,已计算 2,本步写入 0,未计算初值 i=3,面值 1、2、5 0,边界已设 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 计算 dp[2, 4](面值 2、金额 4):重复选 2 元,写入 2 枚
处理第 2 种硬币(面值 2)、金额 a = 4:不选 2 元硬币时为正上方 dp[1, 4] = 4(四枚 1 元);选入 2 元硬币时,从本行左方已更新的 dp[2, 2] = 1(已含 1 枚 2 元)再加 1 得 2(两枚 2 元)。取 min(4, 2) = 2 写入 dp[2, 4],完成第 2 行,体现本行左方转移可重复选取同种硬币。
零钱兑换第 10 步:计算 dp[2, 4]后的完整 dp 表(MAX=5,不可达) 前 i 种硬币及可用面值 金额0 金额1 金额2 金额3 金额4 i=0,无硬币 0,边界已设 MAX,不可达边界 MAX,不可达边界 MAX,不可达边界 MAX,不可达边界 i=1,面值 1 0,边界已设 1,已计算 2,已计算 3,已计算 4,已计算 i=2,面值 1、2 0,边界已设 1,已计算 1,已计算 2,已计算 2,本步写入 i=3,面值 1、2、5 0,边界已设 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 计算 dp[3, 1](面值 5、金额 1):面值过大,继承 1 枚
进入第 3 行,引入第 3 种硬币(面值 5),计算金额 a = 1 的 dp[3, 1]。由于面值 5 大于当前金额 1,无法选入 5 元硬币,直接继承正上方 dp[2, 1] = 1,写入 dp[3, 1] = 1。
零钱兑换第 11 步:计算 dp[3, 1]后的完整 dp 表(MAX=5,不可达) 前 i 种硬币及可用面值 金额0 金额1 金额2 金额3 金额4 i=0,无硬币 0,边界已设 MAX,不可达边界 MAX,不可达边界 MAX,不可达边界 MAX,不可达边界 i=1,面值 1 0,边界已设 1,已计算 2,已计算 3,已计算 4,已计算 i=2,面值 1、2 0,边界已设 1,已计算 1,已计算 2,已计算 2,已计算 i=3,面值 1、2、5 0,边界已设 1,本步写入 0,未计算初值 0,未计算初值 0,未计算初值 计算 dp[3, 2](面值 5、金额 2):面值过大,继承 1 枚
继续处理第 3 种硬币(面值 5)、金额 a = 2:面值 5 仍大于当前金额 2,无法选入 5 元硬币,直接继承正上方 dp[2, 2] = 1,写入 dp[3, 2] = 1。
零钱兑换第 12 步:计算 dp[3, 2]后的完整 dp 表(MAX=5,不可达) 前 i 种硬币及可用面值 金额0 金额1 金额2 金额3 金额4 i=0,无硬币 0,边界已设 MAX,不可达边界 MAX,不可达边界 MAX,不可达边界 MAX,不可达边界 i=1,面值 1 0,边界已设 1,已计算 2,已计算 3,已计算 4,已计算 i=2,面值 1、2 0,边界已设 1,已计算 1,已计算 2,已计算 2,已计算 i=3,面值 1、2、5 0,边界已设 1,已计算 1,本步写入 0,未计算初值 0,未计算初值 计算 dp[3, 3](面值 5、金额 3):面值过大,继承 2 枚
继续处理第 3 种硬币(面值 5)、金额 a = 3:面值 5 大于当前金额 3,无法选入 5 元硬币,直接继承正上方 dp[2, 3] = 2,写入 dp[3, 3] = 2。
零钱兑换第 13 步:计算 dp[3, 3]后的完整 dp 表(MAX=5,不可达) 前 i 种硬币及可用面值 金额0 金额1 金额2 金额3 金额4 i=0,无硬币 0,边界已设 MAX,不可达边界 MAX,不可达边界 MAX,不可达边界 MAX,不可达边界 i=1,面值 1 0,边界已设 1,已计算 2,已计算 3,已计算 4,已计算 i=2,面值 1、2 0,边界已设 1,已计算 1,已计算 2,已计算 2,已计算 i=3,面值 1、2、5 0,边界已设 1,已计算 1,已计算 2,本步写入 0,未计算初值 计算 dp[3, 4](面值 5、金额 4):面值过大,继承 2 枚
处理第 3 种硬币(面值 5)、右下角目标金额 a = 4:由于面值 5 大于金额 4,无法选入 5 元硬币,只能直接继承正上方前两种硬币的解 dp[2, 4] = 2(即两枚 2 元硬币凑成 4 元),写入 dp[3, 4] = 2,全表计算完成。
零钱兑换第 14 步:计算 dp[3, 4]后的完整 dp 表(MAX=5,不可达) 前 i 种硬币及可用面值 金额0 金额1 金额2 金额3 金额4 i=0,无硬币 0,边界已设 MAX,不可达边界 MAX,不可达边界 MAX,不可达边界 MAX,不可达边界 i=1,面值 1 0,边界已设 1,已计算 2,已计算 3,已计算 4,已计算 i=2,面值 1、2 0,边界已设 1,已计算 1,已计算 2,已计算 2,已计算 i=3,面值 1、2、5 0,边界已设 1,已计算 1,已计算 2,已计算 2,本步写入 读取右下角 dp[3, 4],返回最少硬币数 2
全部状态转移结束后,读取右下角高亮格 dp[3, 4] = 2。由于该值不等于不可达标记 MAX(5),直接返回 2 作为恰好凑出 4 元的最少硬币枚数(由两枚 2 元硬币组成;若结果为 MAX 则返回 -1)。本步不再改写任何数值。
零钱兑换第 15 步:返回结果后的完整 dp 表(MAX=5,不可达) 前 i 种硬币及可用面值 金额0 金额1 金额2 金额3 金额4 i=0,无硬币 0,边界已设 MAX,不可达边界 MAX,不可达边界 MAX,不可达边界 MAX,不可达边界 i=1,面值 1 0,边界已设 1,已计算 2,已计算 3,已计算 4,已计算 i=2,面值 1、2 0,边界已设 1,已计算 1,已计算 2,已计算 2,已计算 i=3,面值 1、2、5 0,边界已设 1,已计算 1,已计算 2,已计算 2,返回值
面值 5 大于本表各正金额 1 至 4,因此第 3 行继承前两种硬币的结果。代码在最终值为 MAX 时返回 -1,表示无解。
3. 空间优化¶
零钱兑换的空间优化的处理方式和完全背包问题一致:
def coin_change_dp_comp(coins: list[int], amt: int) -> int:
"""零钱兑换:空间优化后的动态规划"""
n = len(coins)
MAX = amt + 1
# 初始化 dp 表
dp = [MAX] * (amt + 1)
dp[0] = 0
# 状态转移
for i in range(1, n + 1):
# 正序遍历
for a in range(1, amt + 1):
if coins[i - 1] > a:
# 若超过目标金额,则不选硬币 i
dp[a] = dp[a]
else:
# 不选和选硬币 i 这两种方案的较小值
dp[a] = min(dp[a], dp[a - coins[i - 1]] + 1)
return dp[amt] if dp[amt] != MAX else -1
/* 零钱兑换:空间优化后的动态规划 */
int coinChangeDPComp(vector<int> &coins, int amt) {
int n = coins.size();
int MAX = amt + 1;
// 初始化 dp 表
vector<int> dp(amt + 1, MAX);
dp[0] = 0;
// 状态转移
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超过目标金额,则不选硬币 i
dp[a] = dp[a];
} else {
// 不选和选硬币 i 这两种方案的较小值
dp[a] = min(dp[a], dp[a - coins[i - 1]] + 1);
}
}
}
return dp[amt] != MAX ? dp[amt] : -1;
}
/* 零钱兑换:空间优化后的动态规划 */
int coinChangeDPComp(int[] coins, int amt) {
int n = coins.length;
int MAX = amt + 1;
// 初始化 dp 表
int[] dp = new int[amt + 1];
Arrays.fill(dp, MAX);
dp[0] = 0;
// 状态转移
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超过目标金额,则不选硬币 i
dp[a] = dp[a];
} else {
// 不选和选硬币 i 这两种方案的较小值
dp[a] = Math.min(dp[a], dp[a - coins[i - 1]] + 1);
}
}
}
return dp[amt] != MAX ? dp[amt] : -1;
}
/* 零钱兑换:空间优化后的动态规划 */
int CoinChangeDPComp(int[] coins, int amt) {
int n = coins.Length;
int MAX = amt + 1;
// 初始化 dp 表
int[] dp = new int[amt + 1];
Array.Fill(dp, MAX);
dp[0] = 0;
// 状态转移
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超过目标金额,则不选硬币 i
dp[a] = dp[a];
} else {
// 不选和选硬币 i 这两种方案的较小值
dp[a] = Math.Min(dp[a], dp[a - coins[i - 1]] + 1);
}
}
}
return dp[amt] != MAX ? dp[amt] : -1;
}
/* 零钱兑换:动态规划 */
func coinChangeDPComp(coins []int, amt int) int {
n := len(coins)
max := amt + 1
// 初始化 dp 表
dp := make([]int, amt+1)
for i := 1; i <= amt; i++ {
dp[i] = max
}
// 状态转移
for i := 1; i <= n; i++ {
// 正序遍历
for a := 1; a <= amt; a++ {
if coins[i-1] > a {
// 若超过目标金额,则不选硬币 i
dp[a] = dp[a]
} else {
// 不选和选硬币 i 这两种方案的较小值
dp[a] = int(math.Min(float64(dp[a]), float64(dp[a-coins[i-1]]+1)))
}
}
}
if dp[amt] != max {
return dp[amt]
}
return -1
}
/* 零钱兑换:空间优化后的动态规划 */
func coinChangeDPComp(coins: [Int], amt: Int) -> Int {
let n = coins.count
let MAX = amt + 1
// 初始化 dp 表
var dp = Array(repeating: MAX, count: amt + 1)
dp[0] = 0
// 状态转移
for i in 1 ... n {
for a in 1 ... amt {
if coins[i - 1] > a {
// 若超过目标金额,则不选硬币 i
dp[a] = dp[a]
} else {
// 不选和选硬币 i 这两种方案的较小值
dp[a] = min(dp[a], dp[a - coins[i - 1]] + 1)
}
}
}
return dp[amt] != MAX ? dp[amt] : -1
}
/* 零钱兑换:空间优化后的动态规划 */
function coinChangeDPComp(coins, amt) {
const n = coins.length;
const MAX = amt + 1;
// 初始化 dp 表
const dp = Array.from({ length: amt + 1 }, () => MAX);
dp[0] = 0;
// 状态转移
for (let i = 1; i <= n; i++) {
for (let a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超过目标金额,则不选硬币 i
dp[a] = dp[a];
} else {
// 不选和选硬币 i 这两种方案的较小值
dp[a] = Math.min(dp[a], dp[a - coins[i - 1]] + 1);
}
}
}
return dp[amt] !== MAX ? dp[amt] : -1;
}
/* 零钱兑换:空间优化后的动态规划 */
function coinChangeDPComp(coins: Array<number>, amt: number): number {
const n = coins.length;
const MAX = amt + 1;
// 初始化 dp 表
const dp = Array.from({ length: amt + 1 }, () => MAX);
dp[0] = 0;
// 状态转移
for (let i = 1; i <= n; i++) {
for (let a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超过目标金额,则不选硬币 i
dp[a] = dp[a];
} else {
// 不选和选硬币 i 这两种方案的较小值
dp[a] = Math.min(dp[a], dp[a - coins[i - 1]] + 1);
}
}
}
return dp[amt] !== MAX ? dp[amt] : -1;
}
/* 零钱兑换:空间优化后的动态规划 */
int coinChangeDPComp(List<int> coins, int amt) {
int n = coins.length;
int MAX = amt + 1;
// 初始化 dp 表
List<int> dp = List.filled(amt + 1, MAX);
dp[0] = 0;
// 状态转移
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超过目标金额,则不选硬币 i
dp[a] = dp[a];
} else {
// 不选和选硬币 i 这两种方案的较小值
dp[a] = min(dp[a], dp[a - coins[i - 1]] + 1);
}
}
}
return dp[amt] != MAX ? dp[amt] : -1;
}
/* 零钱兑换:空间优化后的动态规划 */
fn coin_change_dp_comp(coins: &[i32], amt: usize) -> i32 {
let n = coins.len();
let max = amt + 1;
// 初始化 dp 表
let mut dp = vec![0; amt + 1];
dp.fill(max);
dp[0] = 0;
// 状态转移
for i in 1..=n {
for a in 1..=amt {
if coins[i - 1] > a as i32 {
// 若超过目标金额,则不选硬币 i
dp[a] = dp[a];
} else {
// 不选和选硬币 i 这两种方案的较小值
dp[a] = std::cmp::min(dp[a], dp[a - coins[i - 1] as usize] + 1);
}
}
}
if dp[amt] != max {
return dp[amt] as i32;
} else {
-1
}
}
/* 零钱兑换:空间优化后的动态规划 */
int coinChangeDPComp(int coins[], int amt, int coinsSize) {
int n = coinsSize;
int MAX = amt + 1;
// 初始化 dp 表
int *dp = malloc((amt + 1) * sizeof(int));
for (int j = 1; j <= amt; j++) {
dp[j] = MAX;
}
dp[0] = 0;
// 状态转移
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超过目标金额,则不选硬币 i
dp[a] = dp[a];
} else {
// 不选和选硬币 i 这两种方案的较小值
dp[a] = myMin(dp[a], dp[a - coins[i - 1]] + 1);
}
}
}
int res = dp[amt] != MAX ? dp[amt] : -1;
// 释放内存
free(dp);
return res;
}
/* 零钱兑换:空间优化后的动态规划 */
fun coinChangeDPComp(coins: IntArray, amt: Int): Int {
val n = coins.size
val MAX = amt + 1
// 初始化 dp 表
val dp = IntArray(amt + 1)
dp.fill(MAX)
dp[0] = 0
// 状态转移
for (i in 1..n) {
for (a in 1..amt) {
if (coins[i - 1] > a) {
// 若超过目标金额,则不选硬币 i
dp[a] = dp[a]
} else {
// 不选和选硬币 i 这两种方案的较小值
dp[a] = min(dp[a], dp[a - coins[i - 1]] + 1)
}
}
}
return if (dp[amt] != MAX) dp[amt] else -1
}
### 零钱兑换:空间优化后的动态规划 ###
def coin_change_dp_comp(coins, amt)
n = coins.length
_MAX = amt + 1
# 初始化 dp 表
dp = Array.new(amt + 1, _MAX)
dp[0] = 0
# 状态转移
for i in 1...(n + 1)
# 正序遍历
for a in 1...(amt + 1)
if coins[i - 1] > a
# 若超过目标金额,则不选硬币 i
dp[a] = dp[a]
else
# 不选和选硬币 i 这两种方案的较小值
dp[a] = [dp[a], dp[a - coins[i - 1]] + 1].min
end
end
end
dp[amt] != _MAX ? dp[amt] : -1
end
可视化运行
14.5.3 零钱兑换问题 II¶
Question
给定 \(n\) 种硬币,第 \(i\) 种硬币的面值为 \(coins[i - 1]\) ,目标金额为 \(amt\) ,每种硬币可以重复选取,问凑出目标金额的硬币组合数量。示例如图 14-26 所示。
图 14-26 零钱兑换问题 II 的示例数据
图解 14-26:零钱兑换 II 的硬币组合数
使用可重复选取的面值 1、2、5 硬币恰好凑出目标金额 5,不计取币顺序时共有 4 种不同组合。
零钱兑换问题 II 同样给定面值为 [1, 2, 5] 的 3 种无限量硬币,但本示例的目标金额设为 amt = 5,且求解目标不再是“最少硬币枚数”,而是统计“恰好凑出目标金额 5 的硬币组合数量”(只改变硬币排列顺序而各面值枚数相同的方案视为同一种组合)。
左上方的硬币表通过向右的粗灰色箭头指向标有“目标金额 amt = 5”的钱袋。下半部分结果框列出“硬币组合数量:4”,并在“硬币组合方案:”右侧逐行画出四个硬币加法算式。
下方第一张表列出输入面值,第二张表按图中算式的顺序列出全部组合。各面值的枚数是对算式中硬币个数的统计,原图未另画这张计数表。
| 编号i | 面值 |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 5 |
| 方案 | 面值1数量 | 面值2数量 | 面值5数量 |
|---|---|---|---|
| 1+1+1+1+1 | 5 | 0 | 0 |
| 1+1+1+2 | 3 | 1 | 0 |
| 1+2+2 | 1 | 2 | 0 |
| 5 | 0 | 0 | 1 |
根据输入补充分类验证:若用面值 5,只能单取 1 枚;若不用面值 5,则面值 2 只能取 2、1、0 枚,分别用 1、3、5 枚面值 1 补足。这样恰有表中的四种无序组合,没有遗漏。
1. 动态规划思路¶
相比于上一题,本题目标是求组合数量,因此子问题变为:前 \(i\) 种硬币能够凑出金额 \(a\) 的组合数量。而 \(dp\) 表仍然是尺寸为 \((n+1) \times (amt + 1)\) 的二维矩阵。
当前状态的组合数量等于不选当前硬币与选当前硬币这两种决策的组合数量之和。状态转移方程为:
当目标金额为 \(0\) 时,无须选择任何硬币即可凑出目标金额,因此应将首列所有 \(dp[i, 0]\) 都初始化为 \(1\) 。当无硬币时,无法凑出任何 \(>0\) 的目标金额,因此首行所有 \(dp[0, a]\) 都等于 \(0\) 。
2. 代码实现¶
def coin_change_ii_dp(coins: list[int], amt: int) -> int:
"""零钱兑换 II:动态规划"""
n = len(coins)
# 初始化 dp 表
dp = [[0] * (amt + 1) for _ in range(n + 1)]
# 初始化首列
for i in range(n + 1):
dp[i][0] = 1
# 状态转移
for i in range(1, n + 1):
for a in range(1, amt + 1):
if coins[i - 1] > a:
# 若超过目标金额,则不选硬币 i
dp[i][a] = dp[i - 1][a]
else:
# 不选和选硬币 i 这两种方案之和
dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]]
return dp[n][amt]
/* 零钱兑换 II:动态规划 */
int coinChangeIIDP(vector<int> &coins, int amt) {
int n = coins.size();
// 初始化 dp 表
vector<vector<int>> dp(n + 1, vector<int>(amt + 1, 0));
// 初始化首列
for (int i = 0; i <= n; i++) {
dp[i][0] = 1;
}
// 状态转移
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超过目标金额,则不选硬币 i
dp[i][a] = dp[i - 1][a];
} else {
// 不选和选硬币 i 这两种方案之和
dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]];
}
}
}
return dp[n][amt];
}
/* 零钱兑换 II:动态规划 */
int coinChangeIIDP(int[] coins, int amt) {
int n = coins.length;
// 初始化 dp 表
int[][] dp = new int[n + 1][amt + 1];
// 初始化首列
for (int i = 0; i <= n; i++) {
dp[i][0] = 1;
}
// 状态转移
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超过目标金额,则不选硬币 i
dp[i][a] = dp[i - 1][a];
} else {
// 不选和选硬币 i 这两种方案之和
dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]];
}
}
}
return dp[n][amt];
}
/* 零钱兑换 II:动态规划 */
int CoinChangeIIDP(int[] coins, int amt) {
int n = coins.Length;
// 初始化 dp 表
int[,] dp = new int[n + 1, amt + 1];
// 初始化首列
for (int i = 0; i <= n; i++) {
dp[i, 0] = 1;
}
// 状态转移
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超过目标金额,则不选硬币 i
dp[i, a] = dp[i - 1, a];
} else {
// 不选和选硬币 i 这两种方案之和
dp[i, a] = dp[i - 1, a] + dp[i, a - coins[i - 1]];
}
}
}
return dp[n, amt];
}
/* 零钱兑换 II:动态规划 */
func coinChangeIIDP(coins []int, amt int) int {
n := len(coins)
// 初始化 dp 表
dp := make([][]int, n+1)
for i := 0; i <= n; i++ {
dp[i] = make([]int, amt+1)
}
// 初始化首列
for i := 0; i <= n; i++ {
dp[i][0] = 1
}
// 状态转移:其余行和列
for i := 1; i <= n; i++ {
for a := 1; a <= amt; a++ {
if coins[i-1] > a {
// 若超过目标金额,则不选硬币 i
dp[i][a] = dp[i-1][a]
} else {
// 不选和选硬币 i 这两种方案之和
dp[i][a] = dp[i-1][a] + dp[i][a-coins[i-1]]
}
}
}
return dp[n][amt]
}
/* 零钱兑换 II:动态规划 */
func coinChangeIIDP(coins: [Int], amt: Int) -> Int {
let n = coins.count
// 初始化 dp 表
var dp = Array(repeating: Array(repeating: 0, count: amt + 1), count: n + 1)
// 初始化首列
for i in 0 ... n {
dp[i][0] = 1
}
// 状态转移
for i in 1 ... n {
for a in 1 ... amt {
if coins[i - 1] > a {
// 若超过目标金额,则不选硬币 i
dp[i][a] = dp[i - 1][a]
} else {
// 不选和选硬币 i 这两种方案之和
dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]]
}
}
}
return dp[n][amt]
}
/* 零钱兑换 II:动态规划 */
function coinChangeIIDP(coins, amt) {
const n = coins.length;
// 初始化 dp 表
const dp = Array.from({ length: n + 1 }, () =>
Array.from({ length: amt + 1 }, () => 0)
);
// 初始化首列
for (let i = 0; i <= n; i++) {
dp[i][0] = 1;
}
// 状态转移
for (let i = 1; i <= n; i++) {
for (let a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超过目标金额,则不选硬币 i
dp[i][a] = dp[i - 1][a];
} else {
// 不选和选硬币 i 这两种方案之和
dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]];
}
}
}
return dp[n][amt];
}
/* 零钱兑换 II:动态规划 */
function coinChangeIIDP(coins: Array<number>, amt: number): number {
const n = coins.length;
// 初始化 dp 表
const dp = Array.from({ length: n + 1 }, () =>
Array.from({ length: amt + 1 }, () => 0)
);
// 初始化首列
for (let i = 0; i <= n; i++) {
dp[i][0] = 1;
}
// 状态转移
for (let i = 1; i <= n; i++) {
for (let a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超过目标金额,则不选硬币 i
dp[i][a] = dp[i - 1][a];
} else {
// 不选和选硬币 i 这两种方案之和
dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]];
}
}
}
return dp[n][amt];
}
/* 零钱兑换 II:动态规划 */
int coinChangeIIDP(List<int> coins, int amt) {
int n = coins.length;
// 初始化 dp 表
List<List<int>> dp = List.generate(n + 1, (index) => List.filled(amt + 1, 0));
// 初始化首列
for (int i = 0; i <= n; i++) {
dp[i][0] = 1;
}
// 状态转移
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超过目标金额,则不选硬币 i
dp[i][a] = dp[i - 1][a];
} else {
// 不选和选硬币 i 这两种方案之和
dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]];
}
}
}
return dp[n][amt];
}
/* 零钱兑换 II:动态规划 */
fn coin_change_ii_dp(coins: &[i32], amt: usize) -> i32 {
let n = coins.len();
// 初始化 dp 表
let mut dp = vec![vec![0; amt + 1]; n + 1];
// 初始化首列
for i in 0..=n {
dp[i][0] = 1;
}
// 状态转移
for i in 1..=n {
for a in 1..=amt {
if coins[i - 1] > a as i32 {
// 若超过目标金额,则不选硬币 i
dp[i][a] = dp[i - 1][a];
} else {
// 不选和选硬币 i 这两种方案之和
dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1] as usize];
}
}
}
dp[n][amt]
}
/* 零钱兑换 II:动态规划 */
int coinChangeIIDP(int coins[], int amt, int coinsSize) {
int n = coinsSize;
// 初始化 dp 表
int **dp = malloc((n + 1) * sizeof(int *));
for (int i = 0; i <= n; i++) {
dp[i] = calloc(amt + 1, sizeof(int));
}
// 初始化首列
for (int i = 0; i <= n; i++) {
dp[i][0] = 1;
}
// 状态转移
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超过目标金额,则不选硬币 i
dp[i][a] = dp[i - 1][a];
} else {
// 不选和选硬币 i 这两种方案之和
dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]];
}
}
}
int res = dp[n][amt];
// 释放内存
for (int i = 0; i <= n; i++) {
free(dp[i]);
}
free(dp);
return res;
}
/* 零钱兑换 II:动态规划 */
fun coinChangeIIDP(coins: IntArray, amt: Int): Int {
val n = coins.size
// 初始化 dp 表
val dp = Array(n + 1) { IntArray(amt + 1) }
// 初始化首列
for (i in 0..n) {
dp[i][0] = 1
}
// 状态转移
for (i in 1..n) {
for (a in 1..amt) {
if (coins[i - 1] > a) {
// 若超过目标金额,则不选硬币 i
dp[i][a] = dp[i - 1][a]
} else {
// 不选和选硬币 i 这两种方案之和
dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]]
}
}
}
return dp[n][amt]
}
### 零钱兑换 II:动态规划 ###
def coin_change_ii_dp(coins, amt)
n = coins.length
# 初始化 dp 表
dp = Array.new(n + 1) { Array.new(amt + 1, 0) }
# 初始化首列
(0...(n + 1)).each { |i| dp[i][0] = 1 }
# 状态转移
for i in 1...(n + 1)
for a in 1...(amt + 1)
if coins[i - 1] > a
# 若超过目标金额,则不选硬币 i
dp[i][a] = dp[i - 1][a]
else
# 不选和选硬币 i 这两种方案之和
dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]]
end
end
end
dp[n][amt]
end
可视化运行
3. 空间优化¶
空间优化处理方式相同,删除硬币维度即可:
def coin_change_ii_dp_comp(coins: list[int], amt: int) -> int:
"""零钱兑换 II:空间优化后的动态规划"""
n = len(coins)
# 初始化 dp 表
dp = [0] * (amt + 1)
dp[0] = 1
# 状态转移
for i in range(1, n + 1):
# 正序遍历
for a in range(1, amt + 1):
if coins[i - 1] > a:
# 若超过目标金额,则不选硬币 i
dp[a] = dp[a]
else:
# 不选和选硬币 i 这两种方案之和
dp[a] = dp[a] + dp[a - coins[i - 1]]
return dp[amt]
/* 零钱兑换 II:空间优化后的动态规划 */
int coinChangeIIDPComp(vector<int> &coins, int amt) {
int n = coins.size();
// 初始化 dp 表
vector<int> dp(amt + 1, 0);
dp[0] = 1;
// 状态转移
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超过目标金额,则不选硬币 i
dp[a] = dp[a];
} else {
// 不选和选硬币 i 这两种方案之和
dp[a] = dp[a] + dp[a - coins[i - 1]];
}
}
}
return dp[amt];
}
/* 零钱兑换 II:空间优化后的动态规划 */
int coinChangeIIDPComp(int[] coins, int amt) {
int n = coins.length;
// 初始化 dp 表
int[] dp = new int[amt + 1];
dp[0] = 1;
// 状态转移
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超过目标金额,则不选硬币 i
dp[a] = dp[a];
} else {
// 不选和选硬币 i 这两种方案之和
dp[a] = dp[a] + dp[a - coins[i - 1]];
}
}
}
return dp[amt];
}
/* 零钱兑换 II:空间优化后的动态规划 */
int CoinChangeIIDPComp(int[] coins, int amt) {
int n = coins.Length;
// 初始化 dp 表
int[] dp = new int[amt + 1];
dp[0] = 1;
// 状态转移
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超过目标金额,则不选硬币 i
dp[a] = dp[a];
} else {
// 不选和选硬币 i 这两种方案之和
dp[a] = dp[a] + dp[a - coins[i - 1]];
}
}
}
return dp[amt];
}
/* 零钱兑换 II:空间优化后的动态规划 */
func coinChangeIIDPComp(coins []int, amt int) int {
n := len(coins)
// 初始化 dp 表
dp := make([]int, amt+1)
dp[0] = 1
// 状态转移
for i := 1; i <= n; i++ {
// 正序遍历
for a := 1; a <= amt; a++ {
if coins[i-1] > a {
// 若超过目标金额,则不选硬币 i
dp[a] = dp[a]
} else {
// 不选和选硬币 i 这两种方案之和
dp[a] = dp[a] + dp[a-coins[i-1]]
}
}
}
return dp[amt]
}
/* 零钱兑换 II:空间优化后的动态规划 */
func coinChangeIIDPComp(coins: [Int], amt: Int) -> Int {
let n = coins.count
// 初始化 dp 表
var dp = Array(repeating: 0, count: amt + 1)
dp[0] = 1
// 状态转移
for i in 1 ... n {
for a in 1 ... amt {
if coins[i - 1] > a {
// 若超过目标金额,则不选硬币 i
dp[a] = dp[a]
} else {
// 不选和选硬币 i 这两种方案之和
dp[a] = dp[a] + dp[a - coins[i - 1]]
}
}
}
return dp[amt]
}
/* 零钱兑换 II:空间优化后的动态规划 */
function coinChangeIIDPComp(coins, amt) {
const n = coins.length;
// 初始化 dp 表
const dp = Array.from({ length: amt + 1 }, () => 0);
dp[0] = 1;
// 状态转移
for (let i = 1; i <= n; i++) {
for (let a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超过目标金额,则不选硬币 i
dp[a] = dp[a];
} else {
// 不选和选硬币 i 这两种方案之和
dp[a] = dp[a] + dp[a - coins[i - 1]];
}
}
}
return dp[amt];
}
/* 零钱兑换 II:空间优化后的动态规划 */
function coinChangeIIDPComp(coins: Array<number>, amt: number): number {
const n = coins.length;
// 初始化 dp 表
const dp = Array.from({ length: amt + 1 }, () => 0);
dp[0] = 1;
// 状态转移
for (let i = 1; i <= n; i++) {
for (let a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超过目标金额,则不选硬币 i
dp[a] = dp[a];
} else {
// 不选和选硬币 i 这两种方案之和
dp[a] = dp[a] + dp[a - coins[i - 1]];
}
}
}
return dp[amt];
}
/* 零钱兑换 II:空间优化后的动态规划 */
int coinChangeIIDPComp(List<int> coins, int amt) {
int n = coins.length;
// 初始化 dp 表
List<int> dp = List.filled(amt + 1, 0);
dp[0] = 1;
// 状态转移
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超过目标金额,则不选硬币 i
dp[a] = dp[a];
} else {
// 不选和选硬币 i 这两种方案之和
dp[a] = dp[a] + dp[a - coins[i - 1]];
}
}
}
return dp[amt];
}
/* 零钱兑换 II:空间优化后的动态规划 */
fn coin_change_ii_dp_comp(coins: &[i32], amt: usize) -> i32 {
let n = coins.len();
// 初始化 dp 表
let mut dp = vec![0; amt + 1];
dp[0] = 1;
// 状态转移
for i in 1..=n {
for a in 1..=amt {
if coins[i - 1] > a as i32 {
// 若超过目标金额,则不选硬币 i
dp[a] = dp[a];
} else {
// 不选和选硬币 i 这两种方案之和
dp[a] = dp[a] + dp[a - coins[i - 1] as usize];
}
}
}
dp[amt]
}
/* 零钱兑换 II:空间优化后的动态规划 */
int coinChangeIIDPComp(int coins[], int amt, int coinsSize) {
int n = coinsSize;
// 初始化 dp 表
int *dp = calloc(amt + 1, sizeof(int));
dp[0] = 1;
// 状态转移
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// 若超过目标金额,则不选硬币 i
dp[a] = dp[a];
} else {
// 不选和选硬币 i 这两种方案之和
dp[a] = dp[a] + dp[a - coins[i - 1]];
}
}
}
int res = dp[amt];
// 释放内存
free(dp);
return res;
}
/* 零钱兑换 II:空间优化后的动态规划 */
fun coinChangeIIDPComp(coins: IntArray, amt: Int): Int {
val n = coins.size
// 初始化 dp 表
val dp = IntArray(amt + 1)
dp[0] = 1
// 状态转移
for (i in 1..n) {
for (a in 1..amt) {
if (coins[i - 1] > a) {
// 若超过目标金额,则不选硬币 i
dp[a] = dp[a]
} else {
// 不选和选硬币 i 这两种方案之和
dp[a] = dp[a] + dp[a - coins[i - 1]]
}
}
}
return dp[amt]
}
### 零钱兑换 II:空间优化后的动态规划 ###
def coin_change_ii_dp_comp(coins, amt)
n = coins.length
# 初始化 dp 表
dp = Array.new(amt + 1, 0)
dp[0] = 1
# 状态转移
for i in 1...(n + 1)
# 正序遍历
for a in 1...(amt + 1)
if coins[i - 1] > a
# 若超过目标金额,则不选硬币 i
dp[a] = dp[a]
else
# 不选和选硬币 i 这两种方案之和
dp[a] = dp[a] + dp[a - coins[i - 1]]
end
end
end
dp[amt]
end