So "DP" is just recursion with memoization? Or an I missing another piece?
Edit: apparently I'm not the only one thinking this: https://news.ycombinator.com/item?id=19395862
Edit: apparently I'm not the only one thinking this: https://news.ycombinator.com/item?id=19395862
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...
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.
Eg: https://www.hackerrank.com/domains/algorithms?filters%5Bsubd...
(I have no affiliation with the site)
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).
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).
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.
+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.
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"?
[1]: https://en.wikipedia.org/wiki/Dynamic_programming#History
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 funny thing is that I'd much rather use something like this back and forth discussion in an interview. It tells me more than a coding test.
This is harder than it sounds though.
DP problems tend to be solvable in only a couple lines of code, but the tough part is deciding what to recurve on, and what to memoize.