动态规划 —— 完全背包问题（题集）

完全背包的四大经典模型#

✅ 模型 1：最值模型 - 求最少硬币数（LeetCode 322）

易场景：凑出目标金额，最少需要多少硬币？

1
int coinChange(vector<int>& coins, int amount) {
2
    const int INF = amount + 1;
3
    vector<int> dp(amount + 1, INF);
4
    dp[0] = 0;
5
    for (int coin : coins)
6
        for (int j = coin; j <= amount; ++j)
7
            dp[j] = min(dp[j], dp[j - coin] + 1);
8
    return dp[amount] == INF ? -1 : dp[amount];
9
}

 示例：coins = {1, 2, 5}, amount = 11 → 输出：3（5 + 5 + 1）

✅ 模型 2：计数模型 - 凑出金额的组合数（LeetCode 518）

易场景：凑出目标金额，有多少种组合方式？

1
int change(int amount, vector<int>& coins) {
2
    vector<int> dp(amount + 1);
3
    dp[0] = 1;
4
    for (int coin : coins)
5
        for (int j = coin; j <= amount; ++j)
6
            dp[j] += dp[j - coin];
7
    return dp[amount];
8
}

 示例：coins = {1, 2, 5}, amount = 5 → 输出：4

（四种组合：5, 2+2+1, 2+1+1+1, 1+1+1+1+1）

✅ 模型 3：可行性模型 - 是否能正好凑出金额

易场景：判断某个金额是否能被某些硬币正好凑出

1
bool canMakeAmount(int amount, vector<int>& coins) {
2
    vector<bool> dp(amount + 1);
3
    dp[0] = true;
4
    for (int coin : coins)
5
        for (int j = coin; j <= amount; ++j)
6
            dp[j] = dp[j] || dp[j - coin];
7
    return dp[amount];
8
}

 示例：coins = {2, 4}, amount = 7 → 输出：false

✅ 模型 4：路径模型 - 恢复最少硬币的选取路径

易场景：不仅要求最少硬币数，还想知道具体用的哪些硬币

1
vector<int> coinChangePath(vector<int>& coins, int amount) {
2
    const int INF = amount + 1;
3
    vector<int> dp(amount + 1, INF);
4
    vector<int> prev(amount + 1, -1);
5
    dp[0] = 0;
6

7
    for (int coin : coins)
8
        for (int j = coin; j <= amount; ++j)
9
            if (dp[j] > dp[j - coin] + 1) {
10
                dp[j] = dp[j - coin] + 1;
11
                prev[j] = j - coin;
12
            }
13

14
    if (dp[amount] == INF) return {}; // 无解
15

16
    // 回溯路径
17
    vector<int> res;
18
    for (int cur = amount; cur > 0; cur = prev[cur])
19
        res.push_back(cur - prev[cur]);
20
    return res;
21
}

 示例：

• 输入：coins = {1, 2, 5}, amount = 11

• 输出：{5, 5, 1}（一组可能的解）

 总结对比表

模型场景 状态表示 转移逻辑 最值模型求最少/最多个数/价值 dp[j] 最小/最大 dp[j] = min(dp[j], dp[j - w] + v) 计数模型统计组合种类 dp[j] 为方案数 dp[j] += dp[j - w] 可行性模型判断是否可达 dp[j] 为 bool `dp[j] = dp[j] 路径模型恢复选法路径 dp[j] + 前驱额外记录 prev[j]，回溯

零钱兑换#

322. 零钱兑换 - 力扣（LeetCode）#

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1。

你可以认为每种硬币的数量是无限的。

示例 1：

1
输入：coins = [1, 2, 5], amount = 11
2
输出：3
3
解释：11 = 5 + 5 + 1

示例 2：

1
输入：coins = [2], amount = 3
2
输出：-1

示例 3：

1
输入：coins = [1], amount = 0
2
输出：0

提示：

1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104

思路#

dp[i] 表示凑出金额 i 所需的最少硬币数，每个硬币个数都是无限的，因此本题是一个完全背包dp。

外层遍历物品（在本题中是硬币）内层遍历背包大小，完全背包是从小到大遍历

递推公式：dp[i] = min(dp[i], dp[i - coin] + 1); 本质上还是选不选硬币coin，在两种选择中选出较小值。思路较为简单因此很容易得出代码

代码#

1
class Solution {
2
public:
3
    int coinChange(vector<int>& coins, int amount) {
4
        const int INF = amount + 1; // 初始化为一个足够大的值
5
        vector<int> dp(amount + 1, INF);
6
        dp[0] = 0; // 凑出金额 0，需要 0 个硬币
7

8
        for (int coin : coins) {
9
            for (int i = coin; i <= amount; ++i) {
10
                dp[i] = min(dp[i], dp[i - coin] + 1);
11
            }
12
        }
13

14
        return dp[amount] == INF ? -1 : dp[amount];
15
    }
16
};

518. 零钱兑换 II - 力扣（LeetCode）#

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

示例 1：

1
输入：amount = 5, coins = [1, 2, 5]
2
输出：4
3
解释：有四种方式可以凑成总金额：
4
5=5
5
5=2+2+1
6
5=2+1+1+1
7
5=1+1+1+1+1

示例 2：

1
输入：amount = 3, coins = [2]
2
输出：0
3
解释：只用面额 2 的硬币不能凑成总金额 3 。

示例 3：

1
输入：amount = 10, coins = [10]
2
输出：1
3
#### 思路
4

5

6
本题就是一个计数模型了，dp[i] 表示凑出金额为 i 的组合数。 dp[i] 表示：凑出金额 i 的组合数。
7

8

9
然后继续外层遍历物品，内层遍历背包容器，完全背包内层顺序便利。然后可以得出代码
10

11

12
#### 代码
13

14

15
```cpp
16
class Solution {
17
public:
18
    int change(int amount, vector<int>& coins) {
19
        int n = coins.size();
20
        vector<unsigned int> dp(amount + 1);
21
        dp[0] = 1;
22
        for (int coin : coins) {
23
            for (int j = coin; j <= amount; j++) {
24
                dp[j] += dp[j - coin];
25
            }
26
        }
27
        return dp[amount];
28
    }
29
};

其他例题#

279. 完全平方数#

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

1
输入：n = 12
2
输出：3
3
解释：12 = 4 + 4 + 4

示例 2：

1
输入：n = 13
2
输出：2
3
解释：13 = 4 + 9

提示：

1 <= n <= 104

思路#

dp[i] 表示和为 i 所需的最少完全平方数的个数。dp[i] = min(dp[i], dp[i - j*j] + 1);

代码#

1
class Solution {
2
public:
3
    int numSquares(int n) {
4
        vector<int> dp(n + 1, INT_MAX);
5
        dp[0] = 0;
6

7
        for (int i = 1; i <= n; i++) {
8
            for (int j = 1; j * j <= i; j++) {
9
                dp[i] = min(dp[i], dp[i - j * j] + 1);
10
            }
11
        }
12
        return dp[n];
13
    }
14
};

1449. 数位成本和为目标值的最大数字#

思路#

设 dp[i] 表示「总花费为 i 时，最多可以构造多少位数字。我们的目标是得到 dp[target] —— 最多可以拼出多少位数。遍历每个 i = 1 ~ target，然后遍历所有数字 d = 1 ~ 9（用下标 0~8 表示），尝试用数字 d 拼出新状态：

1
if (i >= cost[d] && dp[i - cost[d]] != -1) {
2
    dp[i] = max(dp[i], dp[i - cost[d]] + 1);
3
}

含义是：

如果我当前的预算是 i，想加入一个代价为 cost[d] 的数字 d+1，那么我之前的状态得是 i - cost[d]。dp[i - cost[d]] + 1 表示在这个新状态下，数字位数增加了一个。

随后用贪心优先选择大的数填充字符串。

代码#

1
class Solution {
2
public:
3
    string largestNumber(vector<int>& cost, int target) {
4
        vector<int> dp(target + 1, -1); // dp[i] 表示成本为 i 时能构造的最大位数
5
    dp[0] = 0;
6

7
    // 完全背包：构造最多的位数
8
    for (int t = 1; t <= target; ++t) {
9
        for (int d = 0; d < 9; ++d) {
10
            if (t >= cost[d] && dp[t - cost[d]] != -1) {
11
                dp[t] = max(dp[t], dp[t - cost[d]] + 1);
12
            }
13
        }
14
    }
15

16
    if (dp[target] < 0) return "0";
17

18
    // 反向构造最大数（贪心，尽量从9开始选）
19
    string res = "";
20
    int t = target;
21
    for (int d = 8; d >= 0; --d) {
22
        while (t >= cost[d] && dp[t] == dp[t - cost[d]] + 1) {
23
            res += char('1' + d);
24
            t -= cost[d];
25
        }
26
    }
27

28
    return res;
29
    }
30
};

原文发布于 CSDN：动态规划 —— 完全背包问题（题集）