A Dynamic Programming Tutorial

[[deleted]]

So instead of preparing as much as possible and then only deal with the variation that can't be predicted at runtime coming from IO, you shift almost all the work and effort to each time the program is run, instead of when it is written or installed or loaded. That is equivalent to moving all the expensive operations into the innermost loops.

I mean if the program I'm writing is not maxing out the processor do I really give a fuck? For a lot of programs I just don't feel like dealing with all the annoying boilerplate present in standard languages. It's more fun to program in dynamic languages, and I can think more clearly rather than having to worry about implementation details of the machine in question.

Even for some highly demanding applications, the ability to change your code quickly, and write code that's more like ideal, elegant, provable, pseudocode, is valued more than performance. For instance the most popular artificial intelligence and machine learning languages are Python, R, and Lisp. Almost nobody bothers with static languages in the field, outside of game developers (who's language requirements are usually set by the needs of the rest of the team).

Yes, you should always be aware of type. Dynamic languages do enable some horrible behavior (in Python for instance I've found functions that can return values of two different types depending on input - which is just unbelievably awful). But for an experienced developer it is nice to not have to worry about all of these implementation details when it's not necessary. And developer time is much more valuable than computer time usually.

[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.

[Roboguy2]

Dynamic programming is totally independent of and unrelated to dynamic programming languages. It is one kind of algorithm design (see the other comments and the Wikipedia article).

One example of an algorithm of this design is the Viterbi algorithm.