硬币更换Leetcode

Question

问题：https://leetcode.com/problems/coin-change/

解决方案：https://repl.it/@Stylebender/HatefulAliceBlueTransverse#index.js

var coinChange = function(coins, amount) {

    let dp = Array(amount + 1).fill(Infinity); //Fill dp array with dummy values

    dp[0] = 0; 

    for (let i = 1; i <= amount; i++) { 
        for (let j = 0; j < coins.length; j++) { //Iterate through coin denominations
            if (coins[j] <= i) { //Is current coin denomination less than amount? 
                dp[i] = Math.min(dp[i], 1 + dp[i - coins[j]]); 
                //dp array[current amount - coin denomination]
            }
  }
}

return dp[amount] === Infinity ? -1 : dp[amount]; 
};

我理解从“按钮式”构建dp阵列解决方案的一般概念流程，但我只是想知道关于第10行：

dp[i]=数学。最小值（dp[i]，1 dp[i-硬币[j]]；

当你选择当前的第j种硬币面额作为考虑因素时，为什么会出现1？

是因为既然有了有效的硬币面额，我们就解锁了一种新的方法来弥补第i个金额吗？

Answer 1

>

例如，如果0.5以某种方式是最小增量，那么剩下的将变成0.5。

const coinChange = function(coins, amount) {
    const inf = Math.pow(2, 31)
    const dp = []
    dp[0] = 0

    while (dp.length <= amount) {
        let curr = inf - 1
        for (let index = 0; index < coins.length; index++) {

            if (dp.length - coins[index] < 0) {
                continue
            }

            curr = Math.min(curr, 1 + dp[dp.length - coins[index]])
        }

        dp.push(curr)
    }

    return dp[amount] == inf - 1 ? -1 : dp[amount]
};

• 也许用Python更容易掌握：

class Solution:
    def coinChange(self, coins, amount):
        dp = [0] + [float('inf')] * amount
        for index in range(1, amount + 1):
            for coin in coins:
                if index - coin > -1:
                    dp[index] = min(dp[index], dp[index - coin] + 1)
        
        return -1 if dp[-1] == float('inf') else dp[-1]