Dynamic Programming is a concept from control theory in which the goal is to optimize a specific type of equation. Here, "programming" doesn't mean the same word as in "computer programming". It's just a carry over word from the field of optimization and mathematical modeling [0].
Goal is to optimize some problem that can be framed as having the following properties: an optimal solution to the overall problem will result in optimal solutions for all "subproblems" and these "subproblems" are not all disjoint. If they are disjoint, then don't need to use DP, but you can use a simpler divide and conquer approach (example: you don't need DP to solve mergesort)
Such problems are everywhere. Lots of path planning, shortest path type problems are DP based (high level ex: shortest path from A to C going via B necessarily will imply that the path from A to B is the shortest and B to C is the shortest). In reinforcement learning, similar ideas are crucial. Relatedly, in game theory, these types of problems arise in the form of subgame perfect equilibriums.
Thinking graphically, I believe all DPs can be represented as directed acyclical (hyper)graphs. So, the optimal solution on this graph will mean that the subgraphs in the solution also have optimal solutions, and that these subgraphs overlap.
In computer science, the optimizations tend to work incrementally as a 'wavefront' from the smallest subgraph (usually some basecases, starting points) -- using the solution to the current subgraph in the larger subgraph, etc. Eventually, the wavefront covers the relevant parts of the graph. This is what people tend to call "bottom up".
I think many people struggle with understanding "Dynamic Programming." Hopefully the following clears it up for you.
Dynamic Programming can be done using Memoization (top-down; aka recursively) or Tabular method (bottom-up). So what's the difference?
When you see top-down, it means to start from the root of the problem and recursively descend to the base case. As you pop up the stack, you will either calculate and store the result or look up the value in the cache. e.g., in the Fibonacci sequence, check to see if fib(4) was already calculated. No? Calculated and store it so the next time you come across this, you can use the result and not worry about processing fib(1), fib(2), fib(3), etc.
When you see bottom-up, think about filling out a table from the upper left corner column by column then row by row. To speed performance, you'll look at prior values, the value in the column above vs. column to the left vs. or column diagonally to the left. I know this sounds a bit strange, but if you solve the following problems, you'll see a repeating pattern.
Edit Distance
0/1 Knapsack
Rod Cutting
Longest Common Subsequence
Longest Path in Matrix
Coin Change
I've been writing about this in detail. Eventually I'll publish my writing to help others. I solve ~20 problems using Memoization and the Tabular method. As I solve each problem, I compare the solutions with prior problems showing the pattern. What I want to do is help people spot "patterns" vs. memorizing algorithms that are very problem specific.
It seems that many dynamic programming solutions can be arrived at by starting with a recursive formulation, adding memoization, and then optimizing the cache based on specialized knowledge of the problem. For example:
1. Q: How can you compute Fibonacci number f(n) recursively? A: f(n) = f(n-1) + f(n-2)
2. Q: How can you memoize the results of your recursive function(s) to dramatically reduce the number of calls? A: Make a cache keyed on n that stores f(n).
3. Q: Given specialized understanding of the problem, how can you minimize the size of the cache? A: Notice that you don't need to keep all O(n) slots; you only need to keep two ints.
Can every dynamic programming solution be explained this way? Or is there a good example of a dynamic programming problem for which you really need to make a leap that can't be sensibly reached through this sequence of three questions?
2. The meat of the problem is understanding how to formulate it such that this "recursion" is possible.
Point two is often non-trivial so your "just" -- while technically correct -- isn't true in practice. If you solve a variety of medium and difficult DP problems, it will be clear why.
Based on my understanding, the key difference with DP is that you build the solution bottom up instead of top-down.
For example, in case of computing the factorial of 10 recursively, you would start at fact(10) and move down to the base case, fact(1).
With DP, you would start with fact(1) and compute succesive results based on computed ones, all the way up to fact(10).
Following on from this, you usually build up the solution in an array, sequentially, instead of navigating down the tree of solutions and storing as you go (memoization).
I've done a lot of programming contest stuff, and at least when speaking casually, I've always heard DP as referring to either the top-down approach or the bottom-up approach. They have their tradeoffs (though usually top-down is better because it's easier to implement), but they're both DP. It may be that you're technically not supposed to use the term "DP" for the top-down variant, but in practice people use the term to refer to both.
I'd say that in competitive programming, bottom-up is actually preferred.
Bottom up is faster, usually shorter to code, and allows certain kinds of optimizations you can't do with top down (sliding window, convex hull trick, etc).
Top down frees you from needing to think about order of computation, and also allows a different set of optimizations from bottom up (divide & conquer).
TBH it's been a while since I've done these contests seriously, but I remember the "order of computation" problem to be hard to think about for less trivial cases (like with a 3-dimensional table). But maybe I worried about it too much.
And just for fun, while we're listing these things:
Another advantage to bottom-up that I've seen is that sometimes top-down causes your recursion to get so deep that you run out of space in your call stack. Another advantage to top-down is that you're only filling in the subset of the table that's needed for the specific problem you're solving. Certainly someone with a lot of experience should be able to do both.
Some examples where order of computation isn't that trivial is when you're doing DP on trees or a DAG.
+1 to the "filling in a subset" part. Usually it's not too relevant because it's merely a constant factor change, but occasionally it'll be very important.
Sort of. "I know DP" doesn't just mean "I know what memoized recursion is". It means "I know how to take a problem, recognize that DP might help, frame it recursively with highly-overlapping subproblems, and use memoized recursion to implement an efficient algorithm for it". Especially in advanced cases, it take a lot of skill to look at a problem in just the right way that memoized recursion makes it computationally easy.
For example, sometimes you might have a problem where the simple DP approach takes n^3 space, but with some trickery you can get it down to n^2.
Yep, it's still certainly DP, in the same sense that 1 + 1 is addition, but understanding 1 + 1 doesn't necessarily mean that you've mastered addition.
Just trying to understand the concept/name. I'm clearly not the only one confused.
Say I, at runtime, build a table of function pointers. Based on some attribute/test of the input that suggests a specific type of function is faster for that type of input.
If it's faster, but not exponentially faster than a naive solution...is that "dynamic"?
Nope, DP is a bit more than "build a table" or "cache results". It's specifically about framing a problem recursively, and it needs to be the sort of recursion that has overlapping subproblems. For example, fib(8) and fib(7) will both call fib(6), which means that it's useful to cache fib(6). Some problems (like counting the number of nodes in a tree) are recursive but don't have overlapping recursion, so DP doesn't help with those.
(Sorry, I didn't mean my "addition" comment to sound condescending! I just meant that memoized recursive fibonacci is a simple example of DP, and the fact that it's (relatively) simple doesn't mean it's not DP.)
The name "Dynamic Programming" was coined to be deliberately confusing by an early researcher in the field for the sake of maintaining research funding in a hostile environment [1]. Don't worry too much about the components of the name.
Goal is to optimize some problem that can be framed as having the following properties: an optimal solution to the overall problem will result in optimal solutions for all "subproblems" and these "subproblems" are not all disjoint. If they are disjoint, then don't need to use DP, but you can use a simpler divide and conquer approach (example: you don't need DP to solve mergesort)
Such problems are everywhere. Lots of path planning, shortest path type problems are DP based (high level ex: shortest path from A to C going via B necessarily will imply that the path from A to B is the shortest and B to C is the shortest). In reinforcement learning, similar ideas are crucial. Relatedly, in game theory, these types of problems arise in the form of subgame perfect equilibriums.
Thinking graphically, I believe all DPs can be represented as directed acyclical (hyper)graphs. So, the optimal solution on this graph will mean that the subgraphs in the solution also have optimal solutions, and that these subgraphs overlap.
In computer science, the optimizations tend to work incrementally as a 'wavefront' from the smallest subgraph (usually some basecases, starting points) -- using the solution to the current subgraph in the larger subgraph, etc. Eventually, the wavefront covers the relevant parts of the graph. This is what people tend to call "bottom up".
[0] http://web.mit.edu/15.053/www/AppliedMathematicalProgramming...