题目链接
思路
因为硬币数量是无限的,所以无法以硬币数量作为状态进行遍历
代码
class Solution {
public int coinChange(int[] coins, int amount) {
int n = coins.length;
if(n == 0){
return -1;
}
// dp[i] 表示目标金额为 i 的情况下,所使用的最小硬币数量
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for(int i = 1; i <= amount; ++i){
for(int j = 0; j < n; ++j){
if(i - coins[j] >= 0){
// dp[i]有两种实现的方式,
// 一种是包含当前的coins[j],那么剩余钱就是 i-coins[j],这种操作要兑换的硬币数是 dp[i-coins[j]] + 1
// 另一种就是不包含,要兑换的硬币数是dp[i]
dp[i] = Math.min(dp[i - coins[j]] + 1, dp[i]);
}
}
}
return dp[amount] == amount + 1 ? -1 : dp[amount];
}
}
标签:硬币,int,coins,322,amount,Change,Coin,dp
From: https://www.cnblogs.com/shixuanliu/p/17840157.html