Dynamic programming patterns

This chapter covers the DP shapes that come up most, and the details that tell them apart.

Two sequences. For two sequences, a good state is a pair of prefix lengths. Longest Common Subsequence asks for the best answer using the first i items of one and the first j of the other. If the last items match, extend the answer for the shorter prefixes. If not, skip one of the last items. Edit Distance uses the same kind of grid, but with different moves and base cases. Two tables that look alike don't have the same recurrence.

0/1 subset sum. Let reachable[s] say whether some subset of the items so far adds up to s. Update the sums from high to low, so each item is used at most once. Going from low to high lets an item reuse itself, which solves a different problem where items are unlimited.

Counting coin combinations. Put the loop over coins outside the loop over sums. That counts each combination once, in a fixed order. Putting the sums outside and trying every coin last usually counts ordered sequences instead. Decide what you're counting before you pick the loop order.

Interval DP. Define what happens inside a range from l to r, then pick a split point or a last action. Choosing the last action can fix its neighbors and separate the subproblems. Choosing the first action may leave messy interactions. Make sure something, such as the range's length, shrinks in every recursive call.

Tree DP. A child may need to return several answers, one for each choice the parent might make. In House Robber III, return the best total when the current node is taken, and when it's skipped. Taking it forces both children to be skipped. Skipping it lets each child pick whichever is better.

Bitmask DP. A small integer encodes which items are used or visited. For a route through every node, the state might be (used set, last node). That's O(n × 2ⁿ) states and up to O(n² × 2ⁿ) work, so n must be small.

Longest increasing subsequence. There's an O(n²) DP and an O(n log n) method. The faster one stores the smallest possible last value for each length. Those values don't have to form one real subsequence together; they record the best chances to extend. For the same length, a smaller last value always beats a larger one.

Practice: LC 1143 Longest Common Subsequence, LC 72 Edit Distance, LC 416 Partition Equal Subset Sum, LC 518 Coin Change II, LC 494 Target Sum, LC 312 Burst Balloons, LC 337 House Robber III, LC 300 Longest Increasing Subsequence.

Check your understanding: Are you finding the best answer, counting, or checking whether one exists? Does order matter? Can an item be reused? Which value would an in-place update overwrite too early?