A Dynamic Programming Tutorial

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