07 — DP Pattern Recognition¶

Phase 4 | Week 29 | Feb 16 – Feb 22, 2027

Pattern recognition is the meta-skill that turns DP from “I need to remember 50 solutions” into “I need to recognize 7 structures.” Most people never get here — they grind problems without ever building this map. This file is your map. Read it, internalize the trigger phrases for each pattern, then apply the 5-question framework to novel problems. That’s how you walk into an interview cold and still derive the right DP.

The 7-Pattern Taxonomy¶

Every DP problem you encounter on LeetCode Hard or FAANG interviews is one of these. Some are composites. Once you can classify a problem in 2-3 minutes, the rest is mechanical.

Pattern	What You’re Optimizing	State Shape	Trigger Phrase
1D Linear	Something about a 1D sequence	`dp[i]` = answer for first i elements	“contiguous array,” “1D sequence,” “adjacent constraint”
2D Grid	Path/match across two sequences or a grid	`dp[i][j]` = answer for (i,j) position	“two strings,” “edit,” “grid path,” “common subsequence”
Knapsack	Select items under a capacity constraint	`dp[j]` = answer at capacity j	“capacity/weight limit,” “subset sum to X,” “take or skip each item”
Interval	Optimal answer over a contiguous range	`dp[i][j]` = answer for range [i,j]	“subarray,” “split/merge,” “parenthesization,” “balloons”
Subsequence	Longest/shortest subsequence with property	`dp[i]` = LIS/LPS ending at i	“increasing/decreasing subsequence,” “palindromic subsequence”
Tree DP	Optimal answer on a tree structure	`dp[node]` = answer for subtree	“binary tree,” “rob parent-child,” “path in tree”
Bitmask DP	Optimal answer over subsets	`dp[mask]` = answer for subset `mask`	“n ≤ 20,” “visit all,” “assign each,” “permutations of small n”

Pattern Deep-Dives: Triggers, States, Transitions¶

1. 1D Linear DP¶

Trigger phrases: “maximum sum subarray,” “can’t pick adjacent,” “minimum cost along path,” “number of ways to climb.”

State formula: dp[i] = optimal answer considering elements 0..i.

Transition formula: dp[i] = f(dp[i-1], dp[i-2], ..., arr[i]) — depends only on a constant number of previous states.

Key decision: Does the answer at position i depend on just dp[i-1], or on dp[i-1] AND dp[i-2]? (House Robber needs both.) If the “window” is larger, it might still be 1D DP with a wider lookback.

Space optimization signal: If only the last k states matter, you can reduce to O(k) space.

2. 2D Grid / String DP¶

Trigger phrases: “two strings,” “edit distance,” “common subsequence/substring,” “number of paths in grid,” “match pattern.”

State formula: dp[i][j] = optimal answer for text1[0..i-1] and text2[0..j-1], or answer to reach grid cell (i, j).

Transition formula: Usually looks at dp[i-1][j], dp[i][j-1], and/or dp[i-1][j-1].

Key decision: When characters match vs. don’t match → different branches in the recurrence.

3. Knapsack DP¶

Trigger phrases: “budget/capacity,” “at most N items,” “subset that sums to,” “take or skip each element.”

State formula: dp[j] = optimal answer with exactly (or at most) capacity/sum j.

Transition formula: dp[j] = optimize(dp[j], dp[j - weight[i]] + value[i])

Key decision: 0/1 (right-to-left inner loop) vs. unbounded (left-to-right inner loop). Misidentifying this produces silent wrong answers.

4. Interval DP¶

Trigger phrases: “split array,” “merge stones,” “burst balloons,” “parenthesization cost,” “minimum cuts,” “palindrome partition.”

State formula: dp[i][j] = optimal answer for the subarray/subproblem on range [i, j].

Transition formula: dp[i][j] = optimize over k in [i,j]: f(dp[i][k], dp[k+1][j]) (or similar split).

Key decision: What is the “last operation” on range [i, j]? (Not first — last.) The choice of what k represents is the entire design challenge.

Fill order: Always iterate by increasing interval length. Never row-by-row.

5. Subsequence DP¶

Trigger phrases: “longest increasing,” “longest palindromic,” “number of distinct subsequences,” “count subsequences matching.”

State formula: dp[i] = property of the best subsequence ending at index i.

Transition formula: dp[i] = optimize over j < i where condition(j, i): dp[j] + 1

Key decision: LIS is O(n log n) with patience sorting. If the answer asks “length,” use the efficient version. If it asks “count” or “reconstruct,” you may need the O(n²) version.

6. Tree DP¶

Trigger phrases: “binary tree,” “not pick parent and child,” “longest path in tree,” “sum of distances.”

State formula: dp[node] = optimal value for the subtree rooted at node. Often need two values per node: “if included” and “if excluded.”

Transition formula: Computed post-order (children before parent). Parent’s state = function of children’s states.

Key decision: Does the answer require tracking both “include” and “exclude” states at each node? If the parent’s choice is constrained by the child (as in House Robber III), yes.

7. Bitmask DP¶

Trigger phrases: “n ≤ 15/20,” “visit all,” “cover all requirements,” “assign each element exactly once,” “permutations/orderings of small set.”

State formula: dp[mask] = optimal answer for the subset encoded by mask. Often dp[mask][last] to also track the last chosen element.

Transition formula: Try adding each unvisited element to the mask: dp[mask | (1<<j)][j] = optimize(dp[mask][i] + cost[i][j])

Key decision: What additional state beyond the mask do you need? For TSP it’s the last node. For assignment problems it might not be needed.

The 5-Question Framework Applied to 3 Novel Problems¶

Novel Problem 1¶

Given an array of integers, find the length of the longest wiggle subsequence (alternates between increasing and decreasing).

Q1 — What are the states? dp[i][0] = longest wiggle subsequence ending at i with a downward move. dp[i][1] = longest wiggle ending at i with an upward move.

Q2 — What are the transitions?

dp[i][1] = max(dp[j][0] + 1)  for all j < i where nums[j] < nums[i]
dp[i][0] = max(dp[j][1] + 1)  for all j < i where nums[j] > nums[i]

Q3 — Base cases? dp[i][0] = dp[i][1] = 1 for all i.

Q4 — What’s the answer? max(dp[i][0], dp[i][1]) over all i.

Q5 — Can I optimize space? Yes — greedy O(n) solution exists (track last direction), but DP version is more instructive here.

Pattern: 1D Linear / Subsequence DP.

Novel Problem 2¶

Given a list of words, find the number of words that can be formed by concatenating other words in the list.

Q1 — What are the states? dp[i] = True if word[0..i-1] can be formed by concatenating words from the dictionary.

Q2 — What are the transitions?

dp[i] = True if exists j < i such that dp[j] == True and word[j..i-1] is in the dictionary

Q3 — Base cases? dp[0] = True (empty string is trivially formed).

Q4 — What’s the answer? dp[len(word)].

Q5 — Space? O(n) DP array, O(1) extra per word.

Pattern: 1D Linear DP (Word Break variant). Use a hash set for O(1) dictionary lookup.

Novel Problem 3¶

You have n balloons labeled 0..n-1. You can pop balloons in any order. If you pop balloon i, you gain i * left_neighbor * right_neighbor coins. Find the maximum coins from popping all balloons.

Q1 — States? dp[i][j] = maximum coins from popping all balloons strictly between i and j (exclusive). Add sentinel balloons 1 at both ends.

Q2 — Transitions? For each k in (i, j): k is the LAST balloon to pop in this range.

dp[i][j] = max(dp[i][k] + nums[i]*nums[k]*nums[j] + dp[k][j])

Q3 — Base cases? dp[i][j] = 0 when j - i < 2 (no balloons between i and j).

Q4 — Answer? dp[0][n+1].

Q5 — Space? O(n²) DP table; no obvious reduction.

Pattern: Interval DP. (This is Burst Balloons — yes, the same problem, re-presented to test recognition.)

DP vs. Greedy: How to Tell¶

Both DP and greedy apply to problems with optimal substructure. The distinguishing test:

Greedy works if: The locally optimal choice at each step is provably globally optimal. You can verify this via the exchange argument — show that swapping any non-greedy choice with the greedy choice does not improve the solution.

DP is required if: Greedy has a counterexample. The classic case: coin change with denominations [1, 3, 4] and target 6. Greedy gives 4+1+1 = 3 coins. DP gives 3+3 = 2 coins.

Rule of thumb: If you can prove greedy via exchange argument, use greedy (simpler, faster). If you find even one counterexample, use DP. Never trust greedy intuition without a proof or a quick counterexample test.

A second test: overlapping subproblems. Greedy never revisits past decisions. DP solves the same subproblem multiple times (hence memoization). If your recursive solution has overlapping subproblems, it’s DP; if each subproblem is solved exactly once, it might be D&C or greedy.

Common DP Optimizations (Names + Intuition)¶

Divide and Conquer Optimization: Applies when the optimal split point k for dp[i][j] is monotone — i.e., the optimal k for dp[i][j] is always ≥ the optimal k for dp[i][j-1]. Reduces O(n³) interval DP to O(n² log n) or even O(n²). Used in some competitive programming interval DP problems. Not common in FAANG interviews.

Convex Hull Trick (CHT): Applies when the DP transition has the form dp[i] = min over j < i of (dp[j] + cost(i, j)) where cost factors into a linear function of j and i. CHT reduces this from O(n²) to O(n) by maintaining a convex hull of lines. Required for some optimization DP problems in competitive programming (CF Div. 1 C/D). Learn it after you’re comfortable with all 7 patterns.

Knuth’s Optimization: Reduces the O(n³) interval DP recurrence to O(n²) under specific conditions (optimal split point satisfies the quadrangle inequality). Niche but elegant.

Know these names. You don’t need to implement them immediately — but when you encounter a TLE on an interval DP and you can’t reduce complexity, these are the tools to reach for.

The DP Cheat Sheet¶

Use this as a quick-reference during practice. Not a crutch — use it to verify your classification, not to replace reasoning.

PATTERN        | STATE SHAPE      | INNER LOOP          | SPACE OPT?
----------------|------------------|---------------------|------------
1D Linear       | dp[i]            | O(n) forward        | Often O(1)
2D Grid/String  | dp[i][j]         | O(n²) forward       | Often O(n) (1 row)
Knapsack 0/1    | dp[j]            | Right-to-left       | Yes (1D)
Knapsack Unbnd  | dp[j]            | Left-to-right       | Yes (1D)
Interval        | dp[i][j]         | By length, then i   | No (O(n²) table)
Subsequence LIS | dp[i]            | O(n²) or O(n log n) | O(n)
Tree DP         | dp[node]         | Post-order DFS      | Implicit
Bitmask DP      | dp[mask][extra]  | Over 2^n masks      | No (exponential)