动态规划 --- Leedcode 322 零钱兑换问题

题目

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额
所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。示例 1:
输入: coins = [1, 2, 5], amount = 11
输出: 3 
解释: 11 = 5 + 5 + 1示例 2:
输入: coins = [2], amount = 3
输出: -1

解析

var coinChange = function(coins, amount) {
    // dp 数组中的每一个元素i表示：金额i所要的最少硬币个数。// 初始化为amount + 1, amount 金额最多需要硬币数 amount，用 amount + 1 表示无穷。const dp = new Array(amount + 1).fill(amount + 1);dp[0] = 0;// 金额为零时，需要的硬币数为零// 外层循环遍历所有状态的所有取值for(let i = 1;i <= amount;i++){
    // 内层循环选出所有取值的最小值for(let coin of coins) {
    if(i-coin < 0){
    continue;}dp[i] = Math.min(dp[i], dp[i - coin] + 1);}}return dp[amount] === amount + 1? -1: dp[amount];
};