https://leetcode.cn/problems/coin-change/?envType=study-plan-v2&envId=top-100-liked
322. 零钱兑换
已解答
中等
相关标签
相关企业
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。你可以认为每种硬币的数量是无限的。
状态转移方程
dp[i] = min(dp[i], dp[i - coin] + 1)
这题没有用Integer.MAX_VALUE，用了amount+1来表示一个不可达的数，因为凑硬币就算是凑一块一块的也最多只需要amount个，amount+1就可以用来表示凑不出来的情况。
这题不用Integer.MAX_VALUE我看了下给的第二个案例就溢出了，coins =[2]，amount =3。执行 dp[i]=Math.min(dp[i],dp[i-coins[j]]+1);
dp[2]=Math.min(Integer.MAX_VALUE,1)=1
dp[3]=Math.min(dp[3],dp[1]+1)。这里的dp[1]就是Integer.MAX_VALUE，加一直接溢出变成一个负数。dp[3]就是一个很小的负数了。结果就错了。。。。但是上一题就是那个hot100-84完全平方那个题就用了Integer.MAX_VALUE不会溢出，中间应该是有一些数学道理的，我也没理解，不深究了。。。
也可以不用Integer.MAX_VALUE，用一个Integer.MAX_VALUE/2，测试案例正常情况下是到不了这么大的，我试了下能过。见下面的第二种代码
class Solution {public int coinChange(int[] coins, int amount) {int[] dp=new int[amount+1];Arrays.fill(dp,amount+1);dp[0]=0;for(int i=1;i<=amount;i++){for(int j=0;j<coins.length;j++){if(coins[j]<=i){dp[i]=Math.min(dp[i],dp[i-coins[j]]+1);}}}return dp[amount] > amount ? -1: dp[amount];}
}
class Solution {public int coinChange(int[] coins, int amount) {int[] dp = new int[amount+1];for(int i=1;i<=amount;i++){dp[i]=Integer.MAX_VALUE/2;}for(int i=1;i<=amount;i++){for(int j=0;j<coins.length;j++){if(coins[j]<=i){dp[i]=Math.min(dp[i],dp[i-coins[j]]+1);}}}return dp[amount] == Integer.MAX_VALUE/2 ? -1: dp[amount];}
}