LeetCode 322. 零钱兑换
题目
给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回-1。
你可以认为每种硬币的数量是无限的。
示例:
输入:coins = [1, 2, 5], amount = 11
输出:3
解释:11 = 5 + 5 + 1
思路
思路:动态规划,dp[]数组表示组成金额i需要的最少硬币个数
- 数组初始化:
Arrays.fill(dp, amount + 1)
; 相当于给一个最大值,便于后面比较得到最少硬币枚数。dp[0]=0
,组成金额0只需要0枚硬币 - 嵌套循环:
I. 第一个循环for(int i=1; i<amount+1; i++)
从金额1~金额i,最少的硬币数量
II. 第二个循环for (int coin:coins)
,假设使用该面额的硬币,能否组成目标金额。里面的条件是if(coin <= i),因为如果coin>i那么这枚硬币肯定用不上
在if语句中,dp[i]=Math.min(dp[i-coin]+1,dp[i])
,这个递推式的意思是说:如果使用coin的话,此时硬币数量就=1+金额(i-coin)的最少硬币数量
,看看dp[i]
本身和dp[i-coin]+1
哪个更小。 return dp[amount] > amount ? -1 : dp[amount];
也就是如果dp[amount]没有变化,那就表示没有解,否则返回解
结果
class Solution {public int coinChange(int[] coins, int amount) {if (amount == 0) return 0;// 贪心 -> 不可行,因为最优解未必通过贪心结果组成。如果贪心最大面值的硬币,结果可能是由部分小硬币组成的(因为大硬币无法组成目标面额)int[] dp = new int[amount + 1]; // 动态规划数组表示组成目标金额需要几枚硬币// 初始化dp数组Arrays.fill(dp, amount + 1);dp[0] = 0; // 如果组成金额0需要0枚硬币for (int i = 1; i < amount + 1; i++) {for (int coin : coins) { // 每个面额下的硬币if (coin <= i){ // 如果硬币面额 < 当前所需组成的amount// 要么使用coin:此时硬币数量=1+(目标amount-指定面额)硬币数量// 要么不用coin:此时硬币数量=目标amount硬币数量dp[i] = Math.min(dp[i - coin] + 1, dp[i]);}}}return dp[amount] > amount ? -1 : dp[amount];}
}