Untitled

mail@pastecode.io avatar
unknown
javascript
a year ago
481 B
20
Indexable
Never

// change coins using array, tabulation (for optimization)

coins = [3,5,10,15];
amount = 30;
let dic = {};
function change(amount, start, end) {
  let temp = JSON.stringify([amount, start, end]);
  if (temp in dic) {
    return dic[temp];
  }
  if (start === end || amount < 0) {
    return 0;
  }
  if (amount === 0) {
    return 1;
  }
  let a = change(amount - coins[start], start, end);
  let b = change(amount, start + 1, end);
  dic[temp] = a + b;
  return dic[temp];
}