稀碎从零算法笔记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]要存的时minint len = coins.size();// INT_MAX + 1 会越界，所以耍小聪明就 INT_MAX-1vector<int> dp(amount+1,INT_MAX-1);dp[0] = 0;//凑成0元 需要0个coinfor(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];}
};