稀碎从零算法笔记Day28-LeetCode：零钱兑换

前言：鸽了好多天了哈哈哈，虽然C站没更但是LC还是坚持刷的，任重道远啊！(可恶的寝室熄灯)

题型：动态规划

链接：322. 零钱兑换 - 力扣（LeetCode）

来源：LeetCode

题目描述

这道题贪心做不了（例子很简单，思路讲）

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

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

你可以认为每种硬币的数量是无限的。（无限金币 -> 完全背包）

题目样例

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

题目思路

讲一下贪心为什么不可以：其实很简单，举个反例就行——用【10，8，7】来凑出16，当取了10之后直接就结束了

重新审题：①最少数目金币 ②无限金币个数感觉可以从背包问题(完全背包)下手

那么开始构建dp数组：dp[i]的含义：凑齐 i 元需要用到的金币数——那就需要dp[amount+1]，因为我们需要遍历到dp[amount]这个位置嘛

明白这一点，就可以思考递归式：在让dp[0] = 0（0元，不需要coin）的条件下，让 i 从 1开始遍历到amount，恰好有i == coins[j]的话，就可以将dp[i] 更新为dp[i-coins[j] + 1]，表明这么些个数的硬币可以凑出来 i 元。

基本差不多了,这时候思考一下给dp[index]中的元素赋初值了：因为是要求最少金币数，那每次更新dp[index]时，就要 min(dp[i],dp[i-coins[i]] + 1) —— i - coins[i]上一段提到过，主要看会不会发生“恰好凑齐这种情况”。为了便于min后能更新dp数组，需要给dp数组初始化为一个【不可能超越的值】这边笔者直接给两种思路： ① 初始化为INX_MAX(但考虑到 +1 后会越界 int ，因此可以初始化为INT_MAX - 1 ，这样最后的时候看一下dp[amount]是否是“INT_MAX-1”即可)
②的思路就是都初始化为【amount +1】——coins最小为 1 ，表示amount最多用到【amount】个coin，所以当初始化为【amount+1】时，就不需要跟①一样考虑越界的问题了

C++代码

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
    //dp，不能贪心
    //  dp[9]:index为 0-8,表示凑成index所需要用到的金币数
    // 因为求最少，所以dp[index]要存的时min
    int len = coins.size();
    // INT_MAX + 1 会越界，所以耍小聪明就 INT_MAX-1
    vector<int> dp(amount+1,INT_MAX-1);
    dp[0] = 0;//凑成0元 需要0个coin
    for(int i=0;i<len;i++)
    {
        for(int j=1;j<amount+1;j++)
        {
            // j表示要凑的钱
            if(j >= coins[i])
            {
                //如果j刚好等于coins[i]，那么dp[j - coins[i]] = dp[0]，就可以更新dp[j]的值
                dp[j] = min(dp[j],dp[j - coins[i]] + 1);
            }
        }
    }
    // 如过dp[amount]的值没变，说明凑不齐amount金额的硬币
    return dp[amount] == INT_MAX-1 ? -1 : dp[amount];
    }
};