Блог

Проблема: https://leetcode.com/problems/coin-change /

Решение: https://repl.it/@Stylebender/HatefulAliceblueTransversal#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] = Math.min(dp [i], 1 dp[i — монеты [j]]);

Почему при выборе текущего номинала j-й монеты для рассмотрения отображается 1 ?

Это потому, что, поскольку существует действительный номинал монеты, мы открыли новый метод для пополнения i-й суммы?

• Да, это верно. Мы бы приблизились к целевой сумме на один шаг.

• Если, например, 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]