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. An approach, called memoization, records the results of recursive calls, so that subsequent calls to a previously solved subproblem are handled by table look-up.
• Bottom-up (tabulation): Although the problem is formulated recursively, the solution is 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.

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

References

UMD CS451 Lecture 13 by David Mount

MIT 6.006 Lecture 21 by Erik Demaine