AlgoPressAppearance
0322-零钱兑换
https://leetcode.cn/problems/coin-change
给你一个整数数组 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
示例 4：
输入：coins = [1], amount = 1
输出：1
示例 5：
输入：coins = [1], amount = 2
输出：2
提示：
1 <= coins.length <= 12
1 <= coins[i] <= 2^31 - 1
0 <= amount <= 10^4
基本思路
动态规划 定义 dp[i] 表示当前凑得零钱数的最小数量，根据 coins 里面的硬币种类, 比如 1,2,5 那么 dp[i] = min(dp[i-1] + 1,dp[i-2]+1,dp[i-5]+1) 如果 i-硬币额度 < 0 则不能凑成，返回 -1 重点： max 的赋值，如果一直没有找到结果，则 dp[amount] = max 则返回 -1;
参考代码
csharp
public class Solution {
public int CoinChange(int[] coins, int amount) {
int max = amount+1;
if(amount==0){
return 0;
}
int[] dp = new int[amount+1];
for(int i=1;i<=amount;i++){
dp[i] = max;
for(int j=0; j<coins.Length; j++){
if(i-coins[j] < 0){
continue;
}
dp[i] = Math.Min(dp[i],dp[i-coins[j]]+1);
}
//Console.WriteLine("dp[{0}] = {1}",i,dp[i]);
}
return dp[amount] == amount+1 ? -1 : dp[amount];
}
}
参考代码2：重新写了一遍
注意：不能直接赋值为 -1 ，其中详细逻辑还没有想清楚，但是不是所有测试用例能通过 答案：因为-1的时候 Math.Min(dp[i],xxx) 就会选择-1的那个数字，所以之前设置 amount + 1 非常重要，就是为了要保证最大值，然后每次比较选择一个最小值
csharp
public class Solution {
public int CoinChange(int[] coins, int amount) {
// 定义 dp 数组， dp[i] 表示当前数额需要最小的硬币数
// 如果硬币 有1,2,5， 那么 dp[i] 应该等于 min(dp[i-1],dp[i-2],dp[i-5])+1
// 如果扣减了 < 0 那么说明找不到结果 dp[i] = -1
int[] dp = new int[amount+1];
//初始化
dp[0] = 0;
//因为后面我们要选择 min 取得最小数，所以我们使用 amount+1 初始化其他数字
//这样执行 min 的时候不会出错，最后如果dp结果值是 amount+1 说明没有找到合适的硬币，返回-1
for(int i=1; i<=amount; i++){
dp[i] = amount+1;
}
//状态转移
for(int i=1; i<=amount; i++){
for(int j=0; j<coins.Length; j++){
if(i-coins[j] >=0){
dp[i] = Math.Min(dp[i],dp[i-coins[j]]+1);
}
}
}
return dp[amount] == amount+1 ? -1 : dp[amount];
}
}
参考代码3： 复习 2022-04-02
csharp
public class Solution {
public int CoinChange(int[] coins, int amount) {
//完全背包问题
//定义 dp[i] 表示凑成i零钱的钱币个数
int[] dp = new int[amount+1];
for(int i=1; i<=amount; i++){
dp[i] = int.MaxValue;
for(int j=coins.Length-1; j>=0; j--){
if(i == coins[j]){
//如果当前硬币正好==当前金额，则个数为1
dp[i] = 1;
}
else if(i >= coins[j]){
if(dp[i-coins[j]] != int.MaxValue){
//这里需要计算，各种凑成硬币情况的最小值，所以初始 dp[i] 在上面要设置为最大值
dp[i] = Math.Min(dp[i], dp[i-coins[j]] + 1);
}
}
}
}
return dp[amount] == int.MaxValue ? -1 : dp[amount];
}
}
// 注意 i== coins[j] 那个地方可以合并，因为 dp[i - coins[j]] = dp[0] = 0;
// 所以直接可以服用下面的公式
public class Solution {
public int CoinChange(int[] coins, int amount) {
//完全背包问题
//定义 dp[i] 表示凑成i零钱的钱币个数
int[] dp = new int[amount+1];
for(int i=1; i<=amount; i++){
dp[i] = int.MaxValue;
for(int j=coins.Length-1; j>=0; j--){
if(i >= coins[j]){
if(dp[i-coins[j]] != int.MaxValue){
//这里需要计算，各种凑成硬币情况的最小值，所以初始 dp[i] 在上面要设置为最大值
//这里包含了 i == coins[j] 的内容 dp[0] = 0
dp[i] = Math.Min(dp[i], dp[i-coins[j]] + 1);
}
}
}
}
return dp[amount] == int.MaxValue ? -1 : dp[amount];
}
}
复习:20220515
注意几点：
- 题目要求求最小值，默认dp数组初始化为0，所以我们要设置最大值为默认值
- 判断 dp[j-coins[i]] 的时候，如果前面不能凑齐，则还是默认值 int.MaxValue ，那么自己也不用计算，因为 int.MaxValue + 1 会溢出没有意义
- dp[0] = 0 , 用另个硬币可以凑成0
csharp
public class Solution {
public int CoinChange(int[] coins, int amount) {
int[] dp = new int[amount+1]; //dp[j]表示凑成j的硬币最小个数
Array.Fill(dp,int.MaxValue); // 默认初始化为最大值，或者 amount 也行
dp[0] = 0; // 凑成0的硬币数是0
for(int i=0; i<coins.Length; i++){
for(int j=0; j<=amount; j++){
if(j >= coins[i] && dp[j-coins[i]] != int.MaxValue){ //前一种情况必须能凑成，如果是int.MaxValue则不用计算
dp[j] = Math.Min(dp[j],dp[j-coins[i]]+1); //此处因为 dp[j] 默认为0，所以要
}
}
}
return dp[amount] == int.MaxValue? -1 : dp[amount];
}
}
复习：20220630
csharp
public class Solution {
public int CoinChange(int[] coins, int amount) {
//凑零钱，完全背包, dp[i] 表示凑成零钱i需要的最少钱币数
int[] dp = new int[amount+1];
int max = 10001; //根据题意用 amount + 1 表示最大硬币数
Array.Fill(dp, max); //因为要求方案的最小数，所以我们初始化成大值，注意这里防止溢出，取 amount + 1，不要去 coins.Length+1,因为可能超过，比如硬币有1,2,5 全用1的硬币凑
dp[0] = 0; //初始化
for(int i=0; i < coins.Length; i++){ //遍历物品
for(int j=1; j<= amount; j++){ //遍历背包(正向遍历)
if(j == coins[i]){ //如果相等则就是1个
dp[j] = 1;
}
else if(j > coins[i]){
dp[j] = Math.Min(dp[j],dp[j-coins[i]]+1);
}
//Console.WriteLine("dp[{0}]={1}",j,dp[j]);
}
}
return dp[amount] == max ? -1 : dp[amount];
}
}