文章来源：https://www.toymoban.com/news/detail-812727.html
这里使用动态规划，代码简洁更易理解文章来源地址https://www.toymoban.com/news/detail-812727.html
package _322;
import java.util.Arrays;
public class Problem_322_CoinChange {
public int coinChange(int [] conins,int amount){
//1. 状态定义，dp[i]表示凑齐金额为i的时候的最小硬币数量
int dp [] = new int[amount + 1];
//2. 状态初始化，因为比较的是最小值，所以不可能比总金额数更大
Arrays.fill(dp,amount + 1);//或者初始化为Math.MAXVALUE;
//凑齐总金额数为 0 的时候的硬币数量就是不选硬币
dp[0] = 0;
//3. 状态转移
for (int i = 0; i < conins.length; i++) {
for (int c = conins[i]; c <= amount; c++) {
dp[c] = Math.min(dp[c],1 + dp[c - conins[i]]);
}
}
//4. 返回最终需要的状态值
return dp[amount] == amount + 1 ? -1 : dp[amount];
}
}
到了这里，关于力扣 | 322. 零钱兑换的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
