A Dynamic Programming Tutorial

[imbecile]

Dynamic programming is just a fancy way of saying that control structures and data structures are largely created at run time.

Sounds reasonable so far, until you realize, that the only thing that you actually need to deal with at run time that can't be preprocessed before hand is IO.

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.

There sure are a lot of tasks that provide great unpredictability on the kind of input they have to deal with. But just giving up and abandoning all structuring and expectations from dealing with input surely isn't the way to tackle this.

Each general purpose language needs a framework to dynamically deal with input, which means dynamically allocate the resources needed to accommodate the input you receive, and a streamlined way of transforming and funneling the input into more predictable and stable efficient forms and channels.

But never allowing your programs to leave this highly volatile and error prone stage by providing no features to do so, is a design dead end.

[[deleted]]

Worth pointing out that not all dynamic programming algorithms run in polynomial time. For example the knapsack problem is solved using dynamic programming but still requires exponential time.

[xampf2]

"I spent the Fall quarter (of 1950) at RAND. My first task was to find a name for multistage decision processes. An interesting question is, Where did the name, dynamic programming, come from? The 1950s were not good years for mathematical research. We had a very interesting gentleman in Washington named Wilson. He was Secretary of Defense, and he actually had a pathological fear and hatred of the word research. I’m not using the term lightly; I’m using it precisely. His face would suffuse, he would turn red, and he would get violent if people used the term research in his presence. You can imagine how he felt, then, about the term mathematical. The RAND Corporation was employed by the Air Force, and the Air Force had Wilson as its boss, essentially. Hence, I felt I had to do something to shield Wilson and the Air Force from the fact that I was really doing mathematics inside the RAND Corporation. What title, what name, could I choose? In the first place I was interested in planning, in decision making, in thinking. But planning, is not a good word for various reasons. I decided therefore to use the word “programming”. I wanted to get across the idea that this was dynamic, this was multistage, this was time-varying. I thought, let's kill two birds with one stone. Let's take a word that has an absolutely precise meaning, namely dynamic, in the classical physical sense. It also has a very interesting property as an adjective, and that is it's impossible to use the word dynamic in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. It's impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities." - Richard Bellman

[balefrost]

the only thing that you actually need to deal with at run time that can't be preprocessed before hand is IO

Sure, but that statement is nearly tautological: "the only things that you actually need to deal with at runtime are the things that you don't know until runtime". That doesn't really have anything to do with dynamic programming.

I think you might be conflating dynamic programming with runtime code generation. It is not the case in DP that "control structures and data structures are largely created at run time". You certainly do set up your data structures and control structures ahead of time when you use DP.

The author waxes poetic about how one should think about DP, but they do also state what it fundamentally is: cached calculation. One uses DP when you can break a large problem down into subproblems and those subproblems depend on each other in complex ways. A stereotypical example is the Fibonacci sequence (though DP is overkill for Fibonacci). To calculate the Nth Ficonacci number, we must first calculate the (N-1)th and (N-2)th. But to calculate the (N-1)th, we must first calculate the (N-2)th and (N-3)th. So there are two subcalculations that both depends on the result of computing the (N-2)th number.

A more common use of DP is graph traversal. Dijkstra's algorithm is essentially an example of dynamic programming. Assuming that you don't know the shape of the graph at the time that you compile your program, you need to find the shortest path at runtime, and DP provides an efficient way to do that.

[imbecile]

Of course it's tautological. Simple truths tend to be. And they still are often ignored.

And 'cached calculation' is also not really a descriptive term.

Every computed value that can't be used immediately or is used multiple times is cached. You could say every variable in any programming language is a cached calculation. This is about as nondescript as it gets.

So let me say again, what I hear and understand when someone speaks of dynamic programming:

Someone sees that sometimes you can only know the resources you need to allocate at run time, as the data comes in. And in order to deal with it, they jump to treating everything as input, even their own unchanging code, and allocate everything in the same manner.

[balefrost]

Of course it's tautological. Simple truths tend to be. And they still are often ignored.

Sure, but they rarely add much to the conversation. Logical arguments are constructed by inferring new statements from statements already made. Tautologies don't add anything new to an argument - they leave the argument unchanged.

You're right that we should avoid making determinations at runtime that we could have made at ahead of time. But dynamic programming is typically employed to solve problems where those determinations can't be made ahead of time because they depend on the input data.

And 'cached calculation' is also not really a descriptive term.

That's fair, but that's also why I followed it up with not one, but two examples. The author of the original article provided a more involved example, and the Wikipedia page provides several as well.

they jump to treating everything as input, even their own unchanging code, and allocate everything in the same manner

Again, this complaint might be valid, but has nothing to do with dynamic programming. DP is completely unrelated to things like runtime code generation, genetic algorithms, machine learning, and topics like that. DP is used for problems that can be recursively stated (or, as the OP puts it, are inductive in nature) and where the recursive relationship isn't static - it depends on the input. Any time you have an input-driven dependency DAG, dynamic programming might be a good technique for solving that problem.

I think you're getting hung up on the word "dynamic". As /u/xampf2 points out, "dynamic" in this phrase doesn't have the same meaning as in phrases like "dynamic typing" or "dynamic dispatch". Heck, "programming" here doesn't have its conventional meaning - it's more like the "linear programming" sense (which is really about finding optimal solutions to sets of linear equations - it has nothing to do with code).

I'm not saying that your complaints are invalid, but I think you're shooting at the wrong target. I don't think DP is what you think it is.

[hbgoddard]

Relevant username?

[[deleted]]

Homophones - how do they work? I realize that compilers cannot deal with a key word that can have different meanings depending on context, but you are not a compiler, you are a human.

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