Skip to content

Instantly share code, notes, and snippets.

@gartenfeld
Last active August 29, 2015 14:15
Show Gist options
  • Save gartenfeld/6220757c73f9b05e41eb to your computer and use it in GitHub Desktop.
Save gartenfeld/6220757c73f9b05e41eb to your computer and use it in GitHub Desktop.
Iterative solution for the minimal change problem.
var solutions = {},
coins = [1,5,7,9,11];
var process = function (t) {
if (t == 0) {
// solved
return 0;
} else if (t < 0) {
// wrong path; return really large number
return 2e10;
} else if (t in solutions) {
return solutions[t];
} else {
var candidates = [];
for (var i=0; i<coins.length; i++) {
// try each type
var remainder = t - coins[i],
lookUp = process(remainder);
candidates.push(lookUp);
if (lookUp === 0) { break; }
} // for loop
console.log(candidates);
var bottom = Math.min.apply(Math,candidates),
solution = bottom + 1; // at least one coin
solutions[t] = solution;
} // else
return solution;
};
var target = '100';
process(target);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment