Skip to main content
Computer Science

Return to Answer

added 1736 characters in body
Source Link
D.W. ♦
D.W. ♦
  • 165.5k
  • 21
  • 230
  • 490

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

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

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

Source Link
D.W. ♦
D.W. ♦
  • 165.5k
  • 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$).