完全背包解决兑换零钱问题

完全背包：零钱兑换
先来欣赏一下灵神的代码
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
@cache # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
def dfs(i: int, c: int) -> int:
if i < 0:
return 0 if c == 0 else inf
#相当于凑不出来就不选
if c < coins[i]: # 凑得剩余钱没有币值大只能不选
return dfs(i - 1, c)
# 不选 vs 继续选
return min(dfs(i - 1, c), dfs(i, c - coins[i]) + 1)

    ans = dfs(len(coins) - 1, amount)
    return ans if ans < inf else -1

对应 LeetCode 322：零钱兑换。

一、前提条件

题目给：

int* coins;
int coinsSize;
int amount;

含义：

coins[i] 表示第 i 种硬币面额
amount 表示要凑出的总金额

要求：用最少数量的硬币凑出 amount。

注意：每种硬币可以使用无限次。(这就是完全背包。)

二、核心概念

1. 0-1 背包
   每个物品只能选一次。

比如 494 目标和转背包时：

每个 nums[i] 只能选一次。

所以是 0-1 背包。

2. 完全背包
   每个物品可以选无限次。

零钱兑换中：

硬币 1 可以用很多次
硬币 2 可以用很多次
硬币 5 可以用很多次

所以是完全背包。

三、先看看灵神的思路：先想递归

不要一上来想 DP。
先定义递归：

dfs(i, c)

表示：

只考虑 coins[0...i] 这些硬币，
凑出金额 c，
最少需要多少个硬币。

例如：

coins = [1,2,5]
amount = 11

那么：

dfs(2, 11)

表示：

只考虑硬币 1、2、5，
凑出金额 11，
最少需要多少个硬币。

四、当前决策
现在考虑第 i 种硬币：coins[i]

有两个选择。
选择一：不选当前硬币

既然不选 coins[i]，那就只能考虑前面的硬币：

dfs(i - 1, c)
意思是：

不用 coins[i]，
只用 coins[0...i-1]，
凑出 c。
选择二：选当前硬币

如果选了一个 coins[i]，金额减少：

c - coins[i]

硬币数量加 1。

因为完全背包可以重复选当前硬币，所以还是停留在 i：

dfs(i, c - coins[i]) + 1

注意这里是：dfs(i, c - coins[i])

不是：dfs(i - 1, c - coins[i])

因为当前硬币还能继续用。

五、递归方程

所以：

dfs(i, c)=min( dfs(i - 1, c), dfs(i, c - coins[i]) + 1)

含义：不选当前硬币，用i-1个里面的硬币选，和选当前硬币每选一次，要凑的钱款-去币值，然后次数加一

两种情况取最小硬币数。

因为题目问：最少需要多少个硬币

所以这里用：min(...)

六、递归边界

1. 金额刚好凑完
   if (c == 0) return 0;

意思是：凑出 0 元，不需要硬币。

2. 没有硬币可选，或者金额变负
   if (i < 0 || c < 0) return INF;

意思是：凑不出来。

这里不能返回 0。

因为返回 0 会被误认为：

用了 0 个硬币就凑出来了。

所以用一个很大的数：

#define INF 1000000000

表示无解。

七、记忆化搜索

递归会重复计算，所以加：

memo[i][c]

含义：

memo[i][c] = dfs(i, c)

也就是：

只考虑 coins[0...i]，
凑出金额 c，
最少需要多少个硬币。

八、从记忆化搜索翻译成 DP 数组

dfs 返回什么，dp 就表示什么。

递归里：dfs(i, c)

表示：

只考虑 coins[0...i]，
凑出金额 c，
最少需要多少个硬币。

所以 DP 定义：

dp[i][c]

表示：

只考虑 coins[0...i]，
凑出金额 c，
最少需要多少个硬币。

递归方程：

dfs(i, c)=min( dfs(i - 1, c), dfs(i, c - coins[i]) + 1)

翻译成 DP：

dp[i][c]=min( dp[i - 1][c], dp[i][c - coins[i]] + 1)
九、二维 DP 代码

#include <stdlib.h>

#define INF 1000000000

int min(int a, int b) {
return a < b ? a : b;
}

int coinChange(int* coins, int coinsSize, int amount) {
int** dp = malloc(coinsSize * sizeof(int*));

for (int i = 0; i < coinsSize; i++) {
    dp[i] = malloc((amount + 1) * sizeof(int));
}

//动态分配二维数组给dp
for (int i = 0; i < coinsSize; i++) {
for (int c = 0; c <= amount; c++) {
dp[i][c] = INF;
}
}
//先全部初始化成极大值
for (int i = 0; i < coinsSize; i++) {
dp[i][0] = 0;
}
//然后给0定义，默认凑0元需要用0个硬币，本题不是01背包，所以这里的情况是刚好去全凑完是0
for (int c = 1; c <= amount; c++) {
if (c % coins[0] == 0) {
dp[0][c] = c / coins[0];
}
}
//第一行要初始化要不后面无法用前面的值
for (int i = 1; i < coinsSize; i++) {
int x = coins[i];

    for (int c = 1; c <= amount; c++) {
        int notChoose = dp[i - 1][c];

        int choose = INF;
        if (c >= x && dp[i][c - x] != INF) {
            choose = dp[i][c - x] + 1;
        }

//这里就是写dp状态方程
dp[i][c] = min(notChoose, choose);
}
}

int ans = dp[coinsSize - 1][amount];

for (int i = 0; i < coinsSize; i++) {
    free(dp[i]);
}

free(dp);

if (ans == INF) {
    return -1;
}

return ans;

}
一维：
int min(int a , int b ){
if (a<=b){
return a;
}else{return b;
}
}
int coinChange(int* coins,int coinsSize,int amount)
{
int INF = amount + 1;

int* dp = malloc((amount+1)*sizeof(int));

for(int i=0;i<=amount;i++)
{
    dp[i]=INF;
}
dp[0]=0;

for(int i=0;i<coinsSize;i++)
{
    int x = coins[i];

    for(int c=x;c<=amount;c++)
    {
        dp[c]=min(
            dp[c],dp[c-x]+1
            //这里是相当于i-1行被第i行覆盖所以就压缩了一维

            //但是保留了c-x那一列
        );
    }
}

int ans = dp[amount];

free(dp);

return ans==INF ? -1 : ans;

}

十、代码怎么理解？

1. 初始化
   dp[i][0] = 0;

意思是：

不管用前几种硬币，
凑出 0 元都需要 0 个硬币。
2. 第一行初始化
if (c % coins[0] == 0) {
dp[0][c] = c / coins[0];
}

意思是：

只用第 0 种硬币时，
如果金额 c 能被 coins[0] 整除，
就可以凑出来。

例如：

coins[0] = 2

那么：

金额 4 可以用两个 2 凑出
金额 6 可以用三个 2 凑出
金额 3 凑不出
3. 状态转移
int notChoose = dp[i - 1][c];

表示：

不选当前硬币 coins[i]。
int choose = dp[i][c - x] + 1;

表示：

选一个当前硬币 coins[i]。

为什么是 dp[i][c - x]？

因为：完全背包当前硬币可以重复用。

所以选了一个 x 后，还是可以继续用第 i 种硬币。

十一、例题完整讲解

用：

coins = [1, 2, 5]
amount = 5

目标：

凑出 5 元，最少需要几个硬币。

1. DP 表含义
   dp[i][c]

表示：

只使用 coins[0...i]，
凑出金额 c，
最少需要多少个硬币。

列是金额：

c = 0 1 2 3 4 5

行是硬币种类：

i = 0，用硬币 1
i = 1，用硬币 1、2
i = 2，用硬币 1、2、5
2. 初始化第一行：只用硬币 1

只用硬币 1：

凑 0：0 个
凑 1：1 个 1
凑 2：2 个 1
凑 3：3 个 1
凑 4：4 个 1
凑 5：5 个 1

所以第一行：

    0  1  2  3  4  5

coin1 0 1 2 3 4 5
3. 处理硬币 2

现在可以用：

1 和 2
c = 1

凑 1：

不选 2：dp[0][1] = 1
选 2：金额不够，不能选

所以：

dp[1][1] = 1
c = 2

凑 2：

不选 2：dp[0][2] = 2
选 2：dp[1][0] + 1 = 0 + 1 = 1

取最小：

dp[1][2] = 1

对应：

2
c = 3

凑 3：

不选 2：dp[0][3] = 3
选 2：dp[1][1] + 1 = 1 + 1 = 2

取最小：

dp[1][3] = 2

对应：

1 + 2
c = 4

凑 4：

不选 2：dp[0][4] = 4
选 2：dp[1][2] + 1 = 1 + 1 = 2

取最小：

dp[1][4] = 2

对应：

2 + 2

注意这里用了：dp[1][2]

也就是本行的状态。

这说明：

硬币 2 可以重复使用。
c = 5

凑 5：

不选 2：dp[0][5] = 5
选 2：dp[1][3] + 1 = 2 + 1 = 3

取最小：

dp[1][5] = 3

对应：1 + 2 + 2

第二行：

    0  1  2  3  4  5

coin1 0 1 2 3 4 5
coin2 0 1 1 2 2 3
4. 处理硬币 5

现在可以用：

1、2、5
c = 1
不选 5：dp[1][1] = 1
选 5：金额不够

所以：

dp[2][1] = 1
c = 2
不选 5：dp[1][2] = 1
选 5：金额不够

所以：

dp[2][2] = 1
c = 3
不选 5：dp[1][3] = 2
选 5：金额不够

所以：

dp[2][3] = 2
c = 4
不选 5：dp[1][4] = 2
选 5：金额不够

所以：

dp[2][4] = 2
c = 5
不选 5：dp[1][5] = 3
选 5：dp[2][0] + 1 = 0 + 1 = 1

取最小：

dp[2][5] = 1

对应：

5

最终表：

    0  1  2  3  4  5

coin1 0 1 2 3 4 5
coin2 0 1 1 2 2 3
coin5 0 1 1 2 2 1

答案：

dp[2][5] = 1

所以返回：

1
十二、易错点
易错点 1：完全背包选当前物品后，i 不变

完全背包：

选当前硬币：
dp[i][c - coins[i]] + 1

0-1 背包：

选当前物品：
dp[i - 1][c - weight[i]] + value[i]

区别：

完全背包可以重复选，所以还是 i。
0-1 背包只能选一次，所以变成 i - 1。
易错点 2：本题是最小值问题

所以用：

min(...)

不是：

max(...)

也不是：

易错点 3：无解不能用 0 表示

无解要用：

INF

因为：

0 表示真的用了 0 个硬币。

例如：

凑出 0 元，需要 0 个硬币。
易错点 4：第一行要处理好

只用第一种硬币时：

能整除就可以凑出。
不能整除就是 INF。