LCR103-零钱兑换

[AAA611]

LCR103零钱兑换

function coinChange(coins: number[], amount: number): number {
    // dp[i]表示金额为 i 时，需要的最少硬币数
    const dp = Array(amount + 1).fill(Infinity)
    // base case
    dp[0]=0
    // amount:状态（金额）
    for (let i = 1; i <= amount; i++) {
        // coin数组:选择
        for (let j = 0; j < coins.length; j++) {
            if (i - coins[j] < 0) continue
            dp[i] = Math.min(dp[i - coins[j]] + 1, dp[i])
        }
    }
    return dp[amount] === Infinity ? -1 : dp[amount]
};