0
$\begingroup$

I've read conflicting answers for the space complexity of the top down implementation w/ memoization for the classic coin change problem. Would this be O(N * M) space as Interview Cake says https://www.interviewcake.com/question/javascript/coin?section=dynamic-programming-recursion&course=fc1 or O(N) space or LeetCode says https://leetcode.com/articles/coin-change/#approach-2-dynamic-programming-top-down-accepted?

N is the size of amount and M is the number of items in denominations

class Change {
   constructor() {
   this.memo = {};
  }

 changePossibilitiesTopDown(amountLeft, denominations, currentIndex = 0) {

// Check our memo and short-circuit if we've already solved this one
const memoKey = [amountLeft, currentIndex].join(', ');
if (this.memo.hasOwnProperty(memoKey)) {
  console.log('grabbing memo [' + memoKey + ']');
  return this.memo[memoKey];
}

// Base cases:
// We hit the amount spot on. yes!
if (amountLeft === 0) return 1;

// We overshot the amount left (used too many coins)
if (amountLeft < 0) return 0;

// We're out of denominations
if (currentIndex === denominations.length) return 0;

console.log('checking ways to make ' + amountLeft + ' with [' + denominations.slice(currentIndex).join(', ') + ']');

// Choose a current coin
const currentCoin = denominations[currentIndex];

// See how many possibilities we can get
// for each number of times to use currentCoin
let numPossibilities = 0;
while (amountLeft >= 0) {
  numPossibilities += this.changePossibilitiesTopDown(amountLeft, denominations, currentIndex + 1);
  amountLeft -= currentCoin;
}

// Save the answer in our memo so we don't compute it again
this.memo[memoKey] = numPossibilities;
return numPossibilities;
  }
}
$\endgroup$
  • 1
    $\begingroup$ Is there any chance you could replace the code with pseudocode? There's a lot of "syntax" in there that gets in the way of the presentation. $\endgroup$ – David Richerby Sep 8 '18 at 18:49
  • $\begingroup$ The space complexity depends on the algorithm you use. It might be that the reason why those two pages list different space complexities is because they are thinking of two different algorithms. $\endgroup$ – D.W. Sep 8 '18 at 19:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.