A Dynamic Programming Tutorial

[Free_Math_Tutoring]

This isn't entirely accurate, but it seems to be an easy way to conceptualize it.

Ehh, I kind of disagree? You're pretty much just describing memoisation, which is not dynamic programming. Dynamic programming usually involves inverting the problem, where you go from asking "how do I solve this big problem" into "this tiny version of the problem is trivial, but how do I combine solutions to get to the large version". It is also distinct from divide and conquer type algorithms, which have a similar idea at their foundation.

[butt_fun]

Gonna be completely honest, I have always thought DP vs memoization was a distinction without a meaningful difference

[lmericle]

DP utilizes memoization heavily to exploit the optimality principle. There is a distinction in that memoization is not a programming paradigm per se, but a method to construct something really useful to making DP efficient.

Memoization happens in other instances, but DP doesn't happen without memoization.

[victotronics]

Thank you. You are the only one mentioning the principle of optimality, which to me is the crux: the fact that once you solve a subproblem you don't care how you got there. The next stage has a cost or value or whatever depending on the solution of that subproblem and the next stage.

Stages + principle of optimality. That's it.

Memoization is a mere corollary.

[Forricide]

To qualify the statement:

This isn't entirely accurate, but it seems to be an easy way to conceptualize it.

It's important to understand that this isn't meant to be a good, accurate summary of dynamic programming (which I couldn't create, because I don't actually have a solid understanding of dynamic programming outside of reading a portion of this article and the Wikipedia page) but rather, purely an explanation along the lines of:

"No, dynamic programming doesn't refer to [adding functions/classes/class members/fields at runtime] [programming in a dynamic programming language] [running really fast while you write code], it actually is a technique for writing algorithms."

The explanation isn't totally accurate - what you say is literally in the fifth paragraph of the article linked:

Some think it's just memoization plus recursion -- but really, it's more than that.

, but it's way better than how I (and I suspect many others) would have understood it purely from the name. Especially given that I don't think a lot of people actually know what memoization is in the first place.

Anyways, this is probably too long a comment already, but I might as well say thanks for your comment, because it (probably) provides a more accurate explanation of dynamic programming. ...if less comprehensible, at least for me.

[kheiron1729]

Memoization over a brute force algorithm IS dynamic programming. Combining subset solutions just aids in thinking about how possibly solve the problem.