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$
2
  • 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$ Commented Sep 8, 2018 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.
    Commented Sep 8, 2018 at 19:10

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.