力扣题目 --- 零钱兑换
题目描述:
给你一个整数数组 coins
,表示不同面额的硬币;以及一个整数 amount
,表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1
。
你可以认为每种硬币的数量是无限的。
示例 1:
输入:coins =[1, 2, 5]
, amount =11
输出:3
解释:11 = 5 + 5 + 1
示例 2:
输入:coins =[2]
, amount =3
输出:-1
示例 3:
输入:coins = [1], amount = 0 输出:0
思路描述:
考虑到数值为amount的硬币数可以由前面两项之和为amount的硬币数之和来求得。因此,我们可以考虑使用动态规划来解决这个问题。
设置dp数组,其中dp[i]的含义是当amount为i时的最小硬币数。
dp数组的长度是amount+1,初始值为amount,即每一项的最大硬币数。
对于状态转移方程的设计,dp[i]应该由前面dp[indexDp]+1,而需要满足i-indexDp在数组中存在。indexDp=1,...,i,dp[i]取所有可能中的最小值。
dp[0]=0;
if(coins[j]<=dp[i]){
dp[i]=min(dp[i],dp[i-coins[j]]+1);
}
最后返回结果dp[amount]。
如果dp[amount]的值大于amount,说明当前硬币的线性组合无法满足其值等于amount,即不存在。
return dp[amount]>amount?-1:dp[amount];
代码:
class Solution {
public int coinChange(int[] coins, int amount) {
int max=amount+1;
int[] dp=new int[amount+1];
Arrays.fill(dp,max);
dp[0]=0;
for(int i=0;i<=amount;i++){
for(int j=0;j<coins.length;j++){
if(coins[j]<=i){
dp[i]=Math.min(dp[i],dp[i-coins[j]]+1);
}
}
}
return dp[amount]>amount?-1:dp[amount];
}
}