外贸公司没网站,微信网站设计制作,中山手机网站建设,在东莞找工作上哪个网站https://leetcode.cn/problems/coin-change/?envTypestudy-plan-v2envIdtop-100-liked
322. 零钱兑换
已解答
中等
相关标签
相关企业
给你一个整数数组 coins #xff0c;表示不同面额的硬币#xff1b;以及一个整数 amount #xff0c;表示总金额。计算并返回可以凑…https://leetcode.cn/problems/coin-change/?envTypestudy-plan-v2envIdtop-100-liked
322. 零钱兑换
已解答
中等
相关标签
相关企业
给你一个整数数组 coins 表示不同面额的硬币以及一个整数 amount 表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额返回 -1 。你可以认为每种硬币的数量是无限的。状态转移方程 dp[i] min(dp[i], dp[i - coin] 1) 这题没有用Integer.MAX_VALUE用了amount1来表示一个不可达的数因为凑硬币就算是凑一块一块的也最多只需要amount个amount1就可以用来表示凑不出来的情况。 这题不用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[] dpnew int[amount1];Arrays.fill(dp,amount1);dp[0]0;for(int i1;iamount;i){for(int j0;jcoins.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[amount1];for(int i1;iamount;i){dp[i]Integer.MAX_VALUE/2;}for(int i1;iamount;i){for(int j0;jcoins.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];}
}
