Coin Sums - What I call Matrix Magic - Explain?

OK, I solved coinSums after some struggle, using a recursive function that pulled the top coin value then reran itself with the remaining coin values… and it works and passes the test, but uses straight forward logic, like you would typically do it on paper (in fact writing out my solution on paper is how I came up with the algorithm).

But after solving, I checked the solution in the hint, and it’s what I typically call Matrix Magic. I’ve seen solutions like that in the past, and they make my head hurt and my eyes cross.

I can follow the loops, and I see what it’s doing, adding itself to previous values at the interval of the value of the coin in question, and occasionally my mind starts to grasp the big picture, and the pattern at play, but for the life of me I can’t full wrap my head around the logic of why it works. Worse, I can’t wrap my head around how I’d ever come up with that just looking at a problem.

So, is there a name for this kind of algorithm, and a good resource that explains how and why it works, and how to identify when and where to apply it? I’d ask someone to explain it, but shy of a whiteboard with pretty illustrations, and I can’t imagine how it could be put into words that would make more sense than the code itself.

Here was the solution in the hint:
(warning SPOILER ALERT- If you haven’t solved this problem before you should attempt it first)

function coinSums(n) {
  const ways = Array(n + 1).fill(0);
  ways[0] = 1
  for (let x of [1, 2, 5, 10, 20, 50, 100, 200])
    for (let i = x; i <= n; i++)
      ways[i] += ways[i - x];
  return ways[n]
}

coinSums(200);

HERES THE CHALLENGE i’M TALKING ABOUT:

I’ve tried to google this in the past, but not sure what its called, and ended up down a rabbit hole digging into serious Matrix Arithmatic typically used to solve the secrets of the universe.

This is known as a “Bottom Up” approach. You can read more here: https://www.baeldung.com/cs/fibonacci-top-down-vs-bottom-up-dynamic-programming

Cool, I’ll read through that… this seems to be like the difference between traditional math vs common core… looking for the patterns rather than working directly with the numbers.

I don’t know if I necessarily agree with either part of that comparison?

You are directly working with the numbers here, but building them in a different, more efficient way based upon a big picture understanding of the goal.

Maybe… seems like its drawing lines in the matrix where the numbers intersect, and then summing them up to come up with the total. The last time I looked into something similar it was a multi-dim matrix, and the solution was added up based on the intervals where each of the numbers landed or something… but perhaps after my OH,I GET IT moment (which I hope arrives soon) I’ll see it differently.

Well, I understand top/down and bottom/up, but still confused regarding building the matrix… I guess in the second article they call it the tabulation, but doesn’t illustrate it much. I’ve got several papers with arrays drawn all over them trying to figure out why you’d draw ones all the way across, then twos, summing up at intervals, then 5’s, etc… with the last sum magically being your answer, but seems just a clever way to store a sumation for each possible combination type…I’m sure with a bit more chicken scratching I’ll get it.

Thats exactly what it is. With a top-down approach you use the same calculations many, many times. With a bottom-up approach, you make each one of those repeated calculations only once and use that result everywhere it will be needed.

Yeah, its just this array my brain isn’t automatically comprehending… I’m at interation 6 on paper, starting to see how the values layer over each other, every number behind arr[x ] containing sumations of the previous numbers, only applying after their intervals… I’m starting to get it, how 2 x 2’s overlapping 1 x 5’s… I’ll get it, just have to rewrite some neural pathways to get this one to seat properly.

I would start with understanding the Fibonacci example first. The challenge you linked is, roughly speaking, a complicated Fibonacci like sequence.

Yeah, Fib was a little two easy, and doesn’t really involve layering values, I believe I initially solved that bottom up, just stashing the previous two values, but see how it can be done filling in a similar array.

Is there another problem that would be similar in complexity to that coin problem? I know why the array works now, still not sure I could have come up with it from scratch though.

There is a whole set of ‘stairs’ problems that build up to this
https://quanticdev.com/algorithms/dynamic-programming/staircase-problems/

Sweet, homework! Thanks!

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.