LeetCode刷题-动态规划-322.零钱兑换
文章目录
动态规划系列问题
leetcode 322.零钱兑换
题目:
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。
示例 1:
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
示例 2:
输入: coins = [2], amount = 3
输出: -1
说明:
你可以认为每种硬币的数量是无限的。
看到这道题的时候,我最先的思路是创建一个num数组,先sort下coins数组,然后用amount除以数组最大的数并放入num数组,然后amount等于其取余,一直循环,然后如果除到最后amount不等于0,就返回-1,否则返回num数组中数的和。
按照这种思路,写了代码并未通过全部测试用例。原来这种思路没有考虑到不一定要先填满最大的coin,有的amount先填满最大coin不一定能整除完,因此需要换个思路。
正确的思路是:
1、创建一个数组dp[amount+1],里面的元素dp[0]表示要凑0元时所需的最少硬币个数;依次类推dp[amount]表示凑amount元时所需最少硬币个数。
2、那么有对于我们要凑的amount,dp[amount]=min{dp[amount-coin[0]],dp[amount-coin[1]]...}+1;
即将问题转换为要凑amount-coin的最小值。
public class _03零钱兑换 {
public static int coinChange(int[] coins, int amount) {
//创建数组dp存放对应金额需要的最小零钱数
int[] dp=new int[amount+1];
Arrays.fill(dp,-1);//初始化为-1,表示不可到达
dp[0]=0;
for (int i=0;i<=amount;i++){
for (int coin:coins){
//保证i-coin角标可以到达且有意义
if (i>=coin&&dp[i-coin]!=-1){
//保证当前i角标处不可到达或比i-coin角标处值大
if (dp[i]==-1||dp[i]>dp[i-coin]){
dp[i]=dp[i-coin]+1;
}
}
}
}
return dp[amount];
}
public static void main(String[] args) {
//拿之前未通过的测试用例做示范
int[]coin={186,419,83,408};
System.out.println(coinChange(coin,6249));
}
}
通过了,但看了别人写的答案,发现了更好的思路
前面思路类似,但dp[i]=Math.min(dp[i],dp[i-coins[j]]+1);
即达到金额i的最小硬币数应为包含使用硬币coins[j]和不包含两种情况的最小值。
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp=new int[amount+1];//新建数组存放对应金额最少硬币数
//amount为全部硬币为1时的最多硬币数,加1后即为不可达到的个数,用于填充数组
Arrays.fill(dp,amount+1);
dp[0]=0;//初始化金额为0时,最少硬币个数为0;
for (int i=0;i<=amount;i++){
for (int j=0;j<coins.length;j++){
//让dp角标有意义
if (i-coins[j]>=0){
//分两种情况,使用硬币coins[j]和不使用,取最小值
dp[i]=Math.min(dp[i],dp[i-coins[j]]+1);
}
}
}
if(dp[amount]==amount+1){
return -1;
}
return dp[amount];
}
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论