Categories
interview

Coin Change II

The following solution uses “Bottom up dynamic programming” approach.

/**
 * @param {number} amount
 * @param {number[]} coins
 * @return {number}
 */
const change = (amount, coins) => {
  const dp = Array(amount + 1).fill(0);
  dp[0] = 1;
  for (const coin of coins) {
    for (let i = coin; i <= amount; 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