字数统计: 934字   |   阅读时长: 3分

摘要: 最少硬币组合问题，对任意面额集的动态规划算法

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

我们此前详细讲解过背包问题，题目的分类汇总参考 01背包和完全背包题目汇总。其中硬币组合是完全背包的一个经典问题。在完全背包中，每个物品都是不限个数的，我们要做的是在背包容量范围内，拿走的总价值尽可能多。

而硬币组合问题中，每种面值的硬币也是不限个数，我们要做的是拿走的面值总和刚好是给定值，使得硬币的个数最少。从背包的角度看就是，硬币的面值相当于体积，每个硬币的价值都是 1，取走的物品刚好填满背包容量，拿走的总价值尽可能少。

给定一系列可选的面值，以及一个给定的数额，最少用多少枚硬币可以拼凑出给定的数额。当面值集合没有其它条件时，可以用类似完全背包的动态规划解决，本文我们看这个问题。

最少硬币组合问题，动态规划是任意面额集合都成立的算法，当面额集满足某些条件时，可以用贪心算法得到最优解。后续我们讨论一下这个问题，感兴趣的朋友可以参考《算法导论》第三版的习题 16-1。

题目

• 322. 零钱兑换

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

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

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

提示：

1
2
3

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

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

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

示例 3：
输入：coins = [1], amount = 0
输出：0

题解

算法：完全背包、动态规划

面额集为 coins，其面额记为 $c[i], i=0,1,2,\cdot,n-1$，不妨设 $0 < c[0] < c[1] < \cdots < c[n-1]$。

当只使用面值 $c[0],\cdots,c[i]$ 的硬币时，可以凑出金额 $j$ 的最少硬币个数记为 $dp[i][j]$，这样定义的话，边界情况为 $dp[i][0] = 0, i=0,1,\cdots,n-1$。

在 $dp[i][j]$ 这个状态的时候，有两种可能的决策，即是否使用 $c[i]$ 面额，若使用，则问题变为 $dp[i][j - c[i]]$，若不使用，则问题变为 $dp[i-1][j]$，选其最小的即可，于是状态转移方程如下：

由于当推导到 $dp[i][j]$ 时，$dp[i+1][\cdots]$ 的所有状态已经计算完成了，而且 $i$ 这一维的推导方向是从大到小地推的，因此 $i$ 这一维可以通过滚动数组优化。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        using ll = long long;
        if(coins.empty()) return 0;

        int N = coins.size();
        vector<int> dp(amount + 1, INT_MAX);
        dp[0] = 0;
        for(int i = 0; i < N; ++i)
            for(int j = coins[i]; j <= amount; ++j)
                dp[j] = min((ll)dp[j], (ll)dp[j - coins[i]] + 1);
        if(dp[amount] == INT_MAX) return -1;
        return dp[amount];
    }
};