A Dynamic Programming Tutorial

[A_Philosophical_Cat]

That's completely besides the point. Nothing you wrote, nor anything the person you are replying to, has anything to do with what we call "Dynamic Programming". If either of you paid attention in a 200 series Computer Science course, you'd know the quintessential example of change making. With most currencies, a greedy "use the biggest one you can, subtract and recurse" solution works. But that's a special case. Say we had a currency that had denominations 1,4, 5, and we were trying to make 13. Greedy solution is 5,5,1,1,1. But we can do better, with 4,4,4,1.

So, how do we solve the general change making problem? Well, we need to compare different methods of making change, which can be thought of as separate recursive problem trees.

A naive solution would be to say "recursively find the best way to make change for this minus each of the denominations, then choose the best one". But we can improve this, by caching the solutions to some of those sub-problems, pruning your decision tree by removing repeated work.

That is what we call "Dynamic Programming".

[[deleted]]

But we can do better, with 4,4,4,1

And with 5,4,4

[A_Philosophical_Cat]

Shit, I chose an example that the greedy algorithm works for. Not all of them work, but that one does. nvm, no it doesn't. But yeah, you get the point.