[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];
    }
};