What is dynamic programming about?

Question

Sorry in advance if this question sounds dumb...

As far as I know, building an algorithm using dynamic programming works this way:

1. express the problem as a recurrence relation;
2. implement the recurrence relation either via memoization or via a bottom up approach.

As far as I know, I have said everything about dynamic programming. I mean: dynamic programming does not give tools/rules/methods/theorems for expressing recurrence relations, nor for turning them into code.

So, what's special about dynamic programming? What does it give you, other than a vague method for approaching a certain kind of problems?

Answer 1

Dynamic programming gives you a way to think about algorithm design. This is often very helpful.

Memoization and bottom-up methods give you a rule/method for turning recurrence relations into code. Memoization is a relatively simple idea, but the best ideas often are!

Dynamic programming gives you a structured way to think about the running time of your algorithm. The running time is basically determined by two numbers: the number of subproblems you have to solve, and the time it takes to solve each subproblem. This provides a convenient easy way to think about the algorithm design problem. When you have a candidate recurrence relation, you can look at it and very quickly get a sense of what the running time might be (for instance, you can often very quickly tell how many subproblems there will be, which is a lower bound on the running time; if there are exponentially many subproblems you have to solve, then the recurrence probably won't be a good approach). This also helps you rule out candidate subproblem decompositions. For instance, if we have a string $S[1..n]$, defining a subproblem by a prefix $S[1..i]$ or suffix $S[j..n]$ or substring $S[i..j]$ might be reasonable (the number of subproblems is polynomial in $n$), but defining a subproblem by a subsequence of $S$ is not likely to be a good approach (the number of subproblems is exponential in $n$). This lets you prune the "search space" of possible recurrences.

Dynamic programming gives you a structured approach to look for candidate recurrence relations. Empirically, this approach is often effective. In particular, there are some heuristics/common patterns you can recognize for common ways to define subproblems, depending on the type of the input. For instance:

• If the input is a positive integer $n$, one candidate way to define a subproblem is by replacing $n$ with a smaller integer $n'$ (s.t. $0 \le n' \le n$).

• If the input is a string $S[1..n]$, some candidate ways to define a subproblem include: replace $S[1..n]$ with a prefix $S[1..i]$; replace $S[1..n]$ with a suffix $S[j..n]$; replace $S[1..n]$ with a substring $S[i..j]$. (Here the subproblem is determined by the choice of $i,j$.)

• If the input is a list, do the same as you'd do for a string.

• If the input is a tree $T$, one candidate way to define a subproblem is to replace $T$ with any subtree of $T$ (i.e., pick a node $x$ and replace $T$ with the subtree rooted at $x$; the subproblem is determined by the choice of $x$).

• If the input is a pair $(x,y)$, then recursively look at the type of $x$ and the type of $y$ to identify a way to choose a subproblem for each. In other words, one candidate way to define a subproblem is to replace $(x,y)$ by $(x',y')$ where $x'$ is a subproblem for $x$ and $y'$ is a subproblem for $y$. (You can also consider subproblems of the form $(x,y')$ or $(x',y)$.)

And so on. This gives you a very useful heuristic: just by looking at the type signature of the method, you can come up with a list of candidate ways to define subproblems. In other words, just by looking at the problem statement -- looking only at the types of the inputs -- you can come up with a handful of candidate ways to define a subproblem.

This is often very helpful. It doesn't tell you what the recurrence relation is, but when you have a particular choice for how to define the subproblem, often it's not too hard to work out a corresponding recurrence relation. So, it often turns design of a dynamic programming algorithm into a structured experience. You write down on scrap paper a list of candidate ways to define subproblems (using the heuristic above). Then, for each candidate, you try to write down a recurrence relation, and evaluate its running time by counting the number of subproblems and the time spent per subproblem. After trying each candidate, you keep the best one that you were able to find. Providing some structure to the algorithm design process is a major help, as otherwise algorithm design can be intimidating (there's such a huge space of possible approaches, without some structure it can be unclear how to even get started).

Answer 2

Your understanding of dynamic programming is correct (afaik), and your question is justified.

I think the additional design space we get from the kind of recurrences we call "dynamic programming" can best be seen in comparison to other schemata of recursive approaches.

Let's pretend our inputs are arrays $A[1..n]$ for the sake of highlighting the concepts.

1. Inductive Approach

   Here the idea is to make your problem smaller, solve the smaller version and derive a solution for the original one. Schematically,

   $\qquad f(A) = g\bigl( f(A[1..n-c]), A \bigr)$

   with $g$ the function/algorithm that translates the solution.

   Example: Finding superstars in linear time

2. Divide & Conquer

   Partition the input into several smaller parts, solve the problem for each and combine. Schematically (for two parts),

   $\qquad f(A) = g\bigl(f(A[1..c]), f(A[c+1..n]), A\bigr)$.

   Examples: Merge-/Quicksort, Shortest pairwise distance in the plane

3. Dynamic Programming

   Consider all ways of partitioning the problem into smaller problems and pick the best. Schematically (for two parts),

   $\qquad f(A) = \operatorname{best} \Bigl\{ g\bigl(f(A[1..c]), f(A[c+1..n])\bigr) \Bigm| 1 \leq c \leq n-1 \Bigr\}$.

   Examples: Edit distance, Change-making problem

   Important side note: dynamic programming is not brute force! The application of $\operatorname{best}$ in every step reduces the search space considerably.

In a sense, you know less and less statically going from top to bottom, and have to make more and more decisions dynamically.

The lesson from learning about dynamic programming is that it is okay to try all possible partitionings (well, it's required for correctness) because it can still be efficient using memoization.

Answer 3

Here is another slightly different way of phrasing what dynamic programming gives you. Dynamic programming collapses an exponential number of candidate solutions into a polynomial number of equivalence classes, such that the candidate solutions in each class are indistinguishable in some sense.

Let me take as an example the problem of finding the number of increasing subsequences of length $k$ in an array $A$ of lenght $n$. It is useful to partition the set of all subsequences into equivalence classes such that two subsequences belong to the same class if and only if they have the same length and end in the same index. All of the $2^n$ possible subsequences belong to exactly one of the $O(n^2)$ equivalence classes. This partitioning preserves enough information so that we can define a recurrence relation for the sizes of the classes. If $f(i, \ell)$ gives the number of subsequences which end in index $i$ and have length $\ell$, then we have:

$$f(i,\ell) = \sum_{j < i \textrm{ such that} A[j] < A[i]} f(j,\ell-1)$$ $$f(i,1) = 1 \textrm{ for all } i = 1 \ldots n$$

This recurrence solves the problem in time $O(n^2k)$.

Answer 4

Dynamic Programming allows you to trade memory for computation time. Consider the classic example, Fibonacci.

Fibonacci is defined by the recurrence $Fib(n)=Fib(n-1)+Fib(n-2)$. If you solve using this recursion, you end up doing $O(2^n)$ calls to $Fib(\cdot)$, since the recursion tree is a binary tree with height $n$.

Instead, you want to calculate $Fib(2)$, then use this to find $Fib(3)$, use that to find $Fib(4)$, etc. This only takes $O(n)$ time.

DP also provides us with basic techniques for translating a recurrence relation into a bottom-up solution, but these are relatively straightforward (and generally involve using an $m$ dimensional matrix, or a frontier of such a matrix, where $m$ is the number of parameters in the recurrence relation). These are well explained in any text about DP.