[leetcode]322-零钱兑换

马谦马谦马谦

615
文章

17
评论

2020 年 2 月 11 日 22:19:27数据结构和算法评论211字数 699阅读 2 分 19 秒阅读模式

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/coin-change

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

给定不同面额的硬币 coins 和一个总金额 amount 。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1 。

示例 1：

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

示例 2：

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

说明:

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

二、题解

以示例一种的 [1, 2, 5] 三种硬币为例，当要凑到 11 块钱的时候，什么时候硬币个数最小？

只有在凑到 11 之前的硬币最少，凑够 11 的硬币才最少。凑到 11 块一种有三种可能性：

已经有 10 块了，再凑 1 块得到 11 块。
已经有 9 块了，再凑 2 块得到 11 块。
已经有 6 块了，再凑 5 块得到 11 块。

也就是说，手里面当前已经揣了 10 块、 9 块或是 6 块钱，这个时候哪个的硬币数量最少，凑成的 11 块钱硬币才最少。很明显又是一个动态规划，以 dp[i]表示 amount=i 时候的最优解个数，那么 dp[i]的状态转移方程为：

\(\begin{equation} dp(i)= \begin{cases} -1 & amount < 0\\ 0 & amount = 0 \\ min(dp[i-coin1], dp[i-coin2], ...) + 1 & amount > 0\end{cases} \end{equation}\)

三、代码

class Solution {
public:
    int coinChange(vector<int> &coins, int amount) {
        int i, cnt;
        // 初始化为 int 类型的最大值以方便做特殊处理
        vector<int> dp(amount + 1, INT_MAX);

        if (amount < 0)
            return -1;

        dp[0] = 0;
        for (i = 1; i <= amount; i++) {
            for (auto coin: coins) {
                // dp[i - coin] 存在并且有最小值才行
                if (i - coin < 0 || dp[i - coin] == INT_MAX)
                    continue;
                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }
        return dp[amount] == INT_MAX ? -1 : dp[amount];
    }
};