1. question: 零钱兑换(中等) 给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。
你可以认为每种硬币的数量是无限的。
来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/coin-change
示例 1:
1 2 3 输入:coins = [1, 2, 5], amount = 11 输出:3 解释:11 = 5 + 5 + 1
示例 2:
1 2 输入:coins = [2], amount = 3 输出:-1
示例 3:
1 2 输入:coins = [1], amount = 0 输出:0
提示:
1 2 3 1 <= coins.length <= 12 1 <= coins[i] <= 231 - 1 0 <= amount <= 104
2. answers 这道题显然是一道完全背包问题,但是优化目标是元素个数最小值。因此需要设置数组dp[j],保存在当前元素及其前面元素的基础上,在当前容量J下,所能达到总和为J的最小个数。
这道题,最开始想的是,和原来的问题一样,按步骤来就行,因为题目要求,没有结果返回-1,所以初始化数组为-1。并且对于装第一个元素,进行初始化。因为初始化为-1,导致下面的比较十分麻烦。
这里需要注意,递推公式仍然是取决于当前元素到底装不装。有以下几个要点:
如果不能够装,那么保持原状即可,即上一个元素的当前状态;
如果能装,并且装该元素:
如果装,而且回退到的那个空间dp[j-coins[i]]有结果,此时结果数+1;
如果装,但是回退到的那个空间dp[j-coins[i]]没有结果,显然,加上本数也无法满足要求,因此此时结果数为判断是否能够整除本元素【j % coins[i]】,如果能整除,那么就是【j / coins[i]】,如果不能整除,那么就是-1;
如果能装但不装,所以,此时,也是保持上一个状态【注意,在比较取最小值的时候,注意,上一个状态是不是没结果】。
此时,对于23情况,则对比取最小值即可。
在取最小值的时候,需要注意【因为-1这里表示没有结果,而又因为取最小值,所以导致-1和最小值造成了冲突,比较麻烦】:
在比较23的最小值的时候,一定注意23是不是-1,如果是-1,就不用比较了,取值为不是-1的结果即可。
如果不是-1,则需要比较取最小值。
代码如下所示:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 public class Solution_0126_02 { public int coinChange (int [] coins, int amount) { int [] dp = new int [amount + 1 ]; Arrays.fill(dp, -1 ); for (int i = 0 ; i < dp.length; i++) { if (i % coins[0 ] == 0 ) dp[i] = i / coins[0 ]; } dp[0 ] = 0 ; for (int i = 1 ; i < coins.length; i++) { for (int j = 0 ; j < dp.length; j++) { if (j >= coins[i] && dp[j-coins[i]] != -1 && dp[j] != -1 ) dp[j] = Math.min(dp[j], dp[j-coins[i]] + 1 ); else if (j >= coins[i] && dp[j-coins[i]] != -1 && dp[j] == -1 ) dp[j] = dp[j-coins[i]] + 1 ; else if (j >= coins[i] && dp[j] == -1 ) dp[j] = j % coins[i] == 0 ? j / coins[i] : -1 ; else if (j >= coins[i] && dp[j] != -1 ) { int temp = j % coins[i] == 0 ? j / coins[i] : -1 ; if (temp != -1 ) dp[j] = Math.min(temp, dp[j]); } } } return dp[amount]; } public static void main (String[] args) { System.out.println(); Solution_0126_02 s = new Solution_0126_02(); int [] coins = {2 , 5 , 10 , 1 }; int amount = 27 ; System.out.println(s.coinChange(coins, amount)); } }
后续参考了题解,上面的问题在于-1和取最小值有影响,所以可初始化为某个最大数,这样,每次取最小值即可。在最后返回的时候,如果该值是一个最大数(在这个最大数无论如何也无法达到),显然就是没有解。
但是即使初始化为最大数,还有一点需要注意,那就是只有当【回退到的那个空间有解,即不是最大数时,才比较取最小值】;否则,如果该空间没有解,那么本空间也就没有解,直接保留上一个元素的状态即可。
代码如下所示:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 public class Solution_0126 { public int coinChange (int [] coins, int amount) { int max = Integer.MAX_VALUE; int [] dp = new int [amount + 1 ]; for (int j = 0 ; j < dp.length; j++) { dp[j] = max; } dp[0 ] = 0 ; for (int i = 0 ; i < coins.length; i++) { for (int j = coins[i]; j <= amount; j++) { if (dp[j - coins[i]] != max) { dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1 ); } } } return dp[amount] == max ? -1 : dp[amount]; } public static void main (String[] args) { System.out.println(); Solution_0126 s = new Solution_0126(); int [] coins = {2 , 5 , 10 , 1 }; int amount = 27 ; System.out.println(s.coinChange(coins, amount)); } }
3. 备注 参考力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com) ,代码随想录 (programmercarl.com) 。