Leetcode 322.零钱兑换【C++】

地址：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

说明:

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

解题思路

解题思路参考官方题解~

一开始的时候自己尝试做这道题，首先想到的办法是将硬币按面值从小到大排序，然后尽可能多的取面较值大的，最终将不同面值的硬币个数加起来即题解。但后来发现，其实有时候并不是面值越大的越多就符合题意，因为会有取面值小一点的才能组合成总金额的情况，所以这个思路是错误的。

然后我参考了官方的题解的自上而下的动态规划法！

官方题解：https://leetcode-cn.com/problems/coin-change/solution/322-ling-qian-dui-huan-by-leetcode-solution/

首先定义：

• F(S)：组成金额 S 所需的最少硬币数量

• [Cn……Cn-₁]：可选的 n 枚硬币面额值

假设我们知道 F(S) ，即组成金额 S 最少的硬币数，最后一枚硬币的面值是 C。那么由于问题的最优子结构，转移方程应为：F(S) = F(S − C) + 1 。但由于不知道最后一枚硬币的面值是多少，所以需要枚举每个硬币面额值并取其中的最小值。

另外为了避免重复的计算，将每个子问题的答案存在一个数组中进行记忆化，如果下次还要计算这个问题的值直接从数组中取出返回即可，这样能保证每个子问题最多只被计算一次。

代码

class Solution {
public:
    vector<int> count;//用于存储 0~amount 的所有总金额的最少硬币数

    //动态规划（Dynamic programming）
    int dp(vector<int>& coins, int rem) {
        if (rem < 0) return -1;//余额小于0
        if (rem == 0) return 0;//余额等于0
        //如果 count[rem - 1] != 0 说明已获取到组成总金额的最少硬币数
        if (count[rem - 1] != 0)
            return count[rem - 1];
        int Min = INT_MAX;
        //枚举不同面额值得硬币分别使用动态规划法求解
        for (int coin : coins) {
            int res = dp(coins, rem - coin);
            if (res >= 0 && res < Min) {
                Min = res + 1;
            }
        }
        count[rem - 1] = Min == INT_MAX ? -1 : Min;
        return count[rem - 1];
    }
    int coinChange(vector<int>& coins, int amount) {
        if (amount < 1) return 0;//总金额小于1
        count.resize(amount);//将count初始化大小为amount
        return dp(coins, amount);
    }
};