33
$\begingroup$

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?

$\endgroup$
  • 11
    $\begingroup$ Historical factoid (this comment won't help you, but Bellman is actually a good lead if you want to get theory heavy on dynamic programming): when Bellman came up with what is now known as dynamic programming, he called the idea "dynamic programming" because purely theoretic work wouldn't fly with his employer at that time, so he needed something more buzzwordy that couldn't be used in a pejorative manner. $\endgroup$ – G. Bach Sep 15 '15 at 20:03
  • 3
    $\begingroup$ As far as I know it is exactly these two points you mention. It becomes special when it avoids exponential explosion because of overlapping subproblems. That's all. Ah, by the way, my professor prefers "algorithmic paradigm" over "vague method". $\endgroup$ – Hendrik Jan Sep 16 '15 at 0:44
  • $\begingroup$ "Dynamic programming" seems to be mainly a buzzword (that's since lost its buzz). That doesn't mean it's not useful of course. $\endgroup$ – user253751 Sep 16 '15 at 8:55
  • 3
    $\begingroup$ Not worthy of an answer, but to me dynamic programming is definitely "that thing you use when you try to solve a problem recursively, but you end up wasting time revisiting the same subproblems over and over." $\endgroup$ – hobbs Sep 16 '15 at 19:56
  • $\begingroup$ @hobbs: Exactly, but the skill is in finding that initial way of wasting time ;) $\endgroup$ – j_random_hacker Mar 26 at 6:40
27
$\begingroup$

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

$\endgroup$
  • $\begingroup$ So you confirm that dynamic programming does not provide with concrete "procedures" to follow. It's just "a way to think", as you said. Note that I'm not arguing that DP is useless (on the contrary!), I'm just trying to understand if there is something that I am missing or if I should just practice more. $\endgroup$ – hey hey Sep 15 '15 at 20:26
  • $\begingroup$ @heyhey, well, yes... and no. See my revised answer for more elaboration. It's not a silver bullet, but it does provide some semi-concrete procedures that are often helpful (not guaranteed to work, but often do prove helpful). $\endgroup$ – D.W. Sep 15 '15 at 20:43
  • $\begingroup$ Many thanks! By practicing I am getting more and more familiar with some of those "semi-concrete procedures" you are describing. $\endgroup$ – hey hey Sep 15 '15 at 20:48
  • $\begingroup$ "if there are exponentially many subproblems you have to solve, then the recurrence probably won't be a good approach". For many problems there is no known polynomial time algorithm. Why should this be a criterion for using DP? $\endgroup$ – Chiel ten Brinke Sep 16 '15 at 19:44
  • $\begingroup$ @Chiel, it's not a criterion for using DP. If you have a problem where you would be happy with an exponential-time algorithms, then you can ignore that particular parenthetical remark. It's just an example to try to illustrate the general point I was making -- not something you should take too seriously or interpret as a hard-and-fast rule. $\endgroup$ – D.W. Sep 16 '15 at 20:57
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "Pruned Dynamic Programming" (when it applies) proves that trying all possibilities is NOT required for correctness. $\endgroup$ – Ben Voigt Sep 16 '15 at 20:11
  • $\begingroup$ @BenVoigt Of course. I remained deliberately vague about what "all ways to partition" means; you want to rule out as many as possible, of course! (However, even if you try all ways of partitioning you don't get brute force since you only ever investigate combinations of optimal solutions to subproblems, whereas brute-force would investigate all combinations of all solutions.) $\endgroup$ – Raphael Sep 17 '15 at 9:01
  • $\begingroup$ Let us continue this discussion in chat. $\endgroup$ – Apass.Jack Oct 25 '18 at 16:46
5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ You talk only about the memoization part, which misses the point of the question. $\endgroup$ – Raphael Sep 16 '15 at 7:03
  • 1
    $\begingroup$ "Dynamic Programming allows you to trade memory for computation time" is not something I heard when doing undergrad, and it's a great way to look at this subject. This is an intuitive answer with a succinct example. $\endgroup$ – trueshot Sep 16 '15 at 17:04
  • $\begingroup$ @trueshot: Except that sometimes dynamic programming (and particularly, "Pruned Dynamic Programming") is able to reduce both time and space requirements. $\endgroup$ – Ben Voigt Sep 16 '15 at 20:12
  • $\begingroup$ @Ben I didn't say it was a one-to-one trade. You can prune a recurrence tree as well. I posit that I did answer the question, which was, "What does DP get us?" It gets us faster algorithms by trading space for time. I agree that the accepted answer is more thorough, but this is valid as well. $\endgroup$ – Kittsil Sep 17 '15 at 7:18
2
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.