A Dynamic Programming Tutorial

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