Categories
interview

Coin Change 2

/**
 * @param {number} amount
 * @param {number[]} coins
 * @return {number}
 */
const change = (amount, coins) => {
  const dp = [];
  for (let i = 0; i < amount + 1; i++) {
    dp[i] = 0;
  }
  dp[0] = 1;
  for (const [key, coin] of Object.entries(coins)) {
    for (let i = coin; i < amount + 1; i++) {
      dp[i] += dp[i - coin];
    }
  }
  return dp[amount];
};
// Analysis   n - length of coins
//            m - amount
// Time Complexity O(n*m)
// Space Complexity O(m) 

Demo