Cocolib

Appearance

On this page

零钱兑换 ​

TIP

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

思路 ​

用完全背包能够求出凑成总金额所需的总的种类数

js
var coinChange = function(coins, amount) {
    let dp = Array(amount + 1).fill(0)
    let res = []
    dp[0] = 1
    for(let i=0;i<coins.length;i++){
        for(let j=coins[i];j<=amount;j++){
            dp[j] += dp[j-coins[i]]
        }
        res.push([...dp])
    }
    console.log(res)
    return dp[amount]
};

输入：[1,2,5] 11

打印结果：

[     0  1  2  3  4  5  6  7  8  9  10  11
 1： [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ],
 2： [ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6 ],
 3： [ 1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 10, 11 ]
]

但是题目要求我们求出最少的硬币个数，并且要求如果没有任何一种硬币组合能组成总金额，返回 -1

最少的硬币个数 ​

  • dp[j]：凑足总额为j所需钱币的最少个数为dp[j]

  • 递推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);

凑足总额为j - coins[i]的最少个数为dp[j - coins[i]]，那么只需要加上一个钱币coins[i]即dp[j - coins[i]] + 1就是dp[j]（考虑coins[i]）

所以dp[j] 要取所有dp[j - coins[i]] + 1中最小的。

  • 初始化：有dp[j-coins[i]]不是初始最大值时，该位才有选择的必要，所以下标非0的元素都是应该是最大值。
js
var coinChange = function(coins, amount) {
    const INT_MAX = 2e31 - 1
    let dp = Array(amount + 1).fill(INT_MAX)
    let res = []
    dp[0] = 0
    for(let i=0;i<coins.length;i++){
        for(let j=coins[i];j<=amount;j++){
            if( dp[j-coins[i]] != INT_MAX) 
                dp[j] = Math.min(dp[j-coins[i]]+1, dp[j])
        }
        res.push([...dp])
    }
    console.log(res)
    return dp[amount]!=INT_MAX?dp[amount]:-1
};