Skip to main content
1 of 2
D.W.
  • 165.6k
  • 21
  • 230
  • 490

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

D.W.
  • 165.6k
  • 21
  • 230
  • 490