题目链接
322. 零钱兑换
思路
代码
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];
}
}