Dynamic Programming

It looks like black magic if you don't see the underlying graph. -- 6.006

Intro

There is a superficial resemblance to divide-and-conquer, in the sense that it breaks problems down into smaller subproblems, which can be solved recursively. However, unlike divide-and-conquer problems, in which the subproblems are disjoint, in dynamic programming the subproblems typically overlap each other.

Dynamic programming solutions rely on two important structural qualities

• Optimal Substructure: for the global problem to be solved optimally, each subproblem should be solved optimally

• Overlapping Subproblems: while it may be possible subdivide a problem into subproblems in exponentially many different ways, these subproblems overlap each other in such a way that the number of distinct subproblems is reasonably small, ideally polynomial in the input size.

Two Approaches

There are two complementary (but essentially equivalent) ways of viewing how a recursive solution is constructed:

• Top-down (memoization): This approach applies recursion directly to solve the problem. However, due to the overlapping nature of the subproblems, the same recursive call is often made many times. Thus, we can record (or memoize) the results of recursive calls so that subsequent calls to a previously solved subproblem are handled by table look-ups.

• Bottom-up (tabulation): Although the problem is formulated recursively, the solution can be built iteratively by combining the solutions to small subproblems to obtain the solution to larger subproblems. Essentially, we are building up the memoization table in a topological order.

Which approach should we use when solving a DP problem? It's great that we have choices. So we choose the one that will the easiest for the question. For example, if we are able to find the topological ordering easily, then we should use tabulation. In some situations, it is very hard to do the topological sort manually (ex. game dp) so implementing the solution recursively will be easier.

Optimization Problems

How do we identify whether a question is DP? Well, it has to satisfy the two properties above. Optimization questions typically can satisfy these two properties quite easily.

An optimization problem usually can have many possible solutions. We wish to find an optimal solution such that the solution value is optimized (max/min). Note: While there can be more than one optimal solutions, DP typically only helps us to find one of them. Since finding all solutions requires backtracking.

DP In 5 Easy Steps

1. define subproblems (optimal substructures) and count them

2. guess (to solve the subproblems) part of the solution (should take poly-time)

3. write a recurrence relate to the subproblem (time / subproblem)

4. top-down (test acyclic) or bottom-up (topo order)

5. Solve the original problem

Define Subproblems

• Prefixes (removing from the end, left with a prefix) $\forall {i} \; x[:i]$ $\theta(n)$

• Suffixes (removing from the beginning, left with a suffix) $\forall {i} \; x[i:]$ $\theta(n)$

• Substrings (break down into multiple parts) $\forall {i} \; x[i:j]$ $\theta(n^2)$

• Subtrees $\theta(n)$

List of DP Questions

• Coordinate DP

  • 1D

    • Climbing Stairs (Fibonacci)

    • House Robber

  • 2D

    • Manhattan's Map

    • Min Path Sum

    • Unique Paths

    • Jump Game

    • Russian Doll Envelopes

• Sequence DP

  • Single Sequence

    • Word Break

    • Palindrome Partition

  • Double Sequence

    • Longest Common Subsequence

    • Longest Common Substring

    • Edit Distance

    • Interleaving String

    • Regex Matching

• Substring DP

  • Coins III

  • Scramble String

  • Bursts Balloons

  • Stone Game

• Knapsack

  • 0/1 Knapsack

  • Multiple constraints

• Partition DP

  • Maximum Subarray I/II/III

  • Sell Stock IV

• Tree DP

  • House Robber III

  • Tree Vertex Cover

  • K Edit Distance

References

• UMD CS451 Lecture 13 by David Mount
• MIT 6.006 Lecture 21 by Erik Demaine