零钱兑换.md

https://leetcode-cn.com/problems/coin-change/submissions/

思路

f[j] = min(f[j - coins[i]] + 1, f[j])

代码

var coinChange = function(coins, amount) {
    let dp = new Array(amount + 1).fill(Infinity)
    dp[0] = 0
    for (let i = 0; i < coins.length; i++) { // 遍历物品
        for (let j = coins[i]; j <= amount; j++) { // 遍历背包
            if (dp[j - coins[i]] != Infinity) { // 如果dp[j - coins[i]]是初始值则跳过
                dp[j] = Math.min(dp[j - coins[i]] + 1, dp[j]);
            }
        }
    }
    return dp[amount] === Infinity ? -1 : dp[amount]
};

复杂度

时间复杂度：$O(N * amount)$，其中N是物品个数即硬币种类 空间复杂度：$O(amount)$，其中amount为总金额也即背包大小