🤖 leetcode 322. Coin Change | medium | dynamic-programming | javascript

One of the famous dynamic programming problems.

🗒️ Problems

322. Coin Change - LeetCode

You are given an integer array coins representing coins of different denominations
and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount.
If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

🤔 Understand problem

• Given the amount of money, find a minimum number of coins to make up that amount.

🥳 Think differently

• Need to check all possible cases.
• Just use coins to make up that amount.

⬆️ bottom-up : [object Object] array

• dp[amount] : the minimum number of coins with that amount of money

const dp = Array(amount + 1).fill(Infinity);
dp[0] = 0;

🥳⬆️ Think differently

• If you know dp[i - coin] (the minimum number of coins with i-coin amount)
• What is dp[i] ?
  • I used one more coin of the minimum coin usage of i-coin amount dp[i-coin].
  • dp[i] = dp[i-coin] + 1
• dp[i] is the minimum number of all cases
  • Math.min(dp[i], dp[i-coin] + 1)

🔥⬆️ My solution

var coinChange = function (coins, amount) {
  const dp = Array(amount + 1).fill(Infinity);
  dp[0] = 0;

  for (let i = 1; i <= amount; i += 1) {
    for (const coin of coins) {
      if (i - coin < 0) continue;

      dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
    }
  }

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

⬇️ top-down : [object Object]

🥳⬇️ Think differently

• dp(money) : the minimum number of coins to make up money.
  • When not possible, return -1.
  • When possible, it should use one more coin of the previous result: dp(money-coin) + 1.

⬇️ top-down without memoization

var coinChange = function (coins, amount) {
  const dp = (remain) => {
    if (remain < 0) return -1;
    if (remain === 0) return 0;

    let min = Infinity;
    for (const coin of coins) {
      if (remain - coin < 0) continue;

      const res = dp(remain - coin);
      if (res === -1) continue;
      min = Math.min(min, 1 + res);
    }
    return min === Infinity ? -1 : min;
  };

  return dp(amount);
};

🔥⬇️ top-down: My Solution

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function (coins, amount) {
  const cache = {};

  const dp = (remain) => {
    if (remain < 0) return -1;
    if (remain === 0) return 0;
    if (cache[remain] !== undefined) return cache[remain];

    let min = Infinity;
    for (const coin of coins) {
      if (remain - coin < 0) continue;

      const res = dp(remain - coin);
      if (res === -1) continue;
      min = Math.min(min, 1 + res);
    }
    return (cache[remain] = min === Infinity ? -1 : min);
  };

  return dp(amount);
};