沈阳哪家网站做的好,系统之家官网,网站建设与制作区别,寻找网络公司做公司网站升级改版LeetCode 322. 零钱兑换
题目
给你一个整数数组 coins #xff0c;表示不同面额的硬币#xff1b;以及一个整数 amount #xff0c;表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额#xff0c;返回-1。 你可以认为每…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 i1; iamount1; i)从金额1~金额i最少的硬币数量 II. 第二个循环for (int coin:coins)假设使用该面额的硬币能否组成目标金额。里面的条件是if(coin i)因为如果coini那么这枚硬币肯定用不上 在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];}
}
