DP Patterns in Depth

Why We Need DP Patterns & How to Think About It

Dynamic Programming can initially feel like a chaotic collection of 100 different problems, each requiring a completely unique and inspired solution. However, under the surface, almost 90% of all interview DP problems belong to just six core families.

Instead of memorizing dozens of solutions, you only need to learn to recognize these 6 families. Once you spot which family a problem belongs to, the state definition and the recurrence transition reveal themselves naturally. This page serves as your field guide to identifying, analyzing, and coding these patterns.

How to use this page

The DP fundamentals doc gave you the machinery: spot overlapping subproblems, define a state, write the recurrence, memoize or tabulate. This page is the field guide — the six families that nearly every interview DP belongs to. For each: the tell (how to recognize it), the state (what dp[i] means — always say this sentence first), the recurrence, and the canonical problems.

Learning DP by family beats learning it by problem: 20 memorized solutions evaporate under pressure; 6 recurrences you can re-derive don't.

Family 1 — 0/1 Knapsack (take it or leave it)

Tell: items with values/weights/costs, a capacity or budget, each item usable once, maximize/minimize or "can you hit exactly X?"

State: dp[i][w] = best value using the first i items within capacity w. The choice at every cell is binary: take item i, or don't.

# 0/1 Knapsack
# Python
def knapsack(values, weights, cap):
    n = len(values)
    dp = [[0] * (cap + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(cap + 1):
            dp[i][w] = dp[i-1][w]                       # skip item i
            if weights[i-1] <= w:                       # take item i (once!)
                dp[i][w] = max(dp[i][w],
                               dp[i-1][w - weights[i-1]] + values[i-1])
    return dp[n][cap]

// Java
public int knapsack(int[] values, int[] weights, int cap) {
    int n = values.length;
    int[][] dp = new int[n + 1][cap + 1];
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= cap; w++) {
            dp[i][w] = dp[i - 1][w];                    // skip item i
            if (weights[i - 1] <= w) {
                dp[i][w] = Math.max(dp[i][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]); // take
            }
        }
    }
    return dp[n][cap];
}

// C++
#include <vector>
#include <algorithm>

int knapsack(const std::vector<int>& values, const std::vector<int>& weights, int cap) {
    int n = values.size();
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(cap + 1, 0));
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= cap; w++) {
            dp[i][w] = dp[i - 1][w];                    // skip item i
            if (weights[i - 1] <= w) {
                dp[i][w] = std::max(dp[i][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]); // take
            }
        }
    }
    return dp[n][cap];
}

The family's disguises are the point — none of these say "knapsack":

• Partition Equal Subset Sum — "can you split into two equal halves?" = knapsack with capacity total/2, values irrelevant.
• Target Sum (+/− signs) — algebra reduces it to subset-sum.
• Coin Change — the unbounded variant: items reusable. The entire code change is iterating w with dp[i][...] referring to the same row (or, in 1-D form: loop coins outer, amounts inner). Know precisely why greedy fails here — it's the classic pairing question.

Space note worth saying aloud: row i only reads row i−1, so 2-D collapses to 1-D — iterate w downward for 0/1 (so you don't reuse item i twice), upward for unbounded. That direction detail is a favorite probe.

Family 2 — LIS (longest increasing subsequence)

Tell: "longest/best subsequence with an ordering condition" — increasing numbers, envelopes that nest, chains that link.

State: dp[i] = length of the best increasing subsequence ending exactly at i. The "ending at" is the trick — it makes the recurrence local:

# LIS O(n²)
# Python
def lis(nums):
    dp = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):              # any earlier, smaller element
            if nums[j] < nums[i]:       # ...can precede nums[i]
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp) if nums else 0

// Java
public int lis(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int[] dp = new int[nums.length];
    java.util.Arrays.fill(dp, 1);
    int maxLen = 1;
    for (int i = 0; i < nums.length; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        maxLen = Math.max(maxLen, dp[i]);
    }
    return maxLen;
}

// C++
#include <vector>
#include <algorithm>

int lis(const std::vector<int>& nums) {
    if (nums.empty()) return 0;
    std::vector<int> dp(nums.size(), 1);
    int maxLen = 1;
    for (size_t i = 0; i < nums.size(); i++) {
        for (size_t j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = std::max(dp[i], dp[j] + 1);
            }
        }
        maxLen = std::max(maxLen, dp[i]);
    }
    return maxLen;
}

The O(n log n) upgrade — patience sorting: keep tails[k] = the smallest possible tail of any increasing subsequence of length k+1; for each number, binary-search its slot and replace. Worth knowing as a concept + library call; deriving it live is rarely demanded.

Disguises: Russian Doll Envelopes (sort by width asc, height desc for ties — the desc breaks same-width chains; then LIS on heights), longest divisible subset, maximum chain of pairs.

Family 3 — LCS (two sequences aligned)

Tell: two strings/arrays compared — longest common anything, edit distance, "make these equal with minimum operations."

State: dp[i][j] = answer for prefixes a[:i] and b[:j]. The recurrence forks on whether the current characters match:

# LCS
# Python
def lcs(a, b):
    dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1          # match: extend the diagonal
            else:
                dp[i][j] = max(dp[i-1][j],           # drop a char from a...
                               dp[i][j-1])           # ...or from b
    return dp[-1][-1]

// Java
public int lcs(String a, String b) {
    int m = a.length(), n = b.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (a.charAt(i - 1) == b.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;     // match
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // mismatch
            }
        }
    }
    return dp[m][n];
}

// C++
#include <string>
#include <vector>
#include <algorithm>

int lcs(std::string a, std::string b) {
    int m = a.length(), n = b.length();
    std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (a[i - 1] == b[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;     // match
            } else {
                dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]); // mismatch
            }
        }
    }
    return dp[m][n];
}

Edit distance (Levenshtein) is the same grid with three transitions (insert/delete/replace, each cost 1) — and the family's production celebrity: spell-checkers, git diff, DNA alignment, fuzzy search (your ⌘K palette's cousin). Other members: shortest common supersequence, delete-operations-to-make-equal, longest palindromic subsequence (LCS of s and reversed s — a lovely reduction to state out loud).

Watch the LCS table fill cell by cell — diagonal jump on a match, max of top/left otherwise:

Family 4 — Grid paths

Tell: a 2-D grid, moving right/down (or 4-directionally with no cycles), count paths or optimize a path cost.

State: dp[r][c] = answer arriving at cell (r, c); transition pulls from top and left. Unique Paths, Minimum Path Sum, obstacle variants — the gentlest family, and the one where bottom-up tabulation feels most natural. (You met the idea in Level 1's nested loops; this is it grown up.) Watch the edges: first row/column have only one incoming direction.

Family 5 — Interval DP

Tell: the answer for a range depends on answers for sub-ranges, and the decision is "where do I split / what happens last in this interval?" — burst balloons, matrix-chain multiplication, palindrome partitioning, stone games.

State: dp[i][j] = best for the interval i…j; iterate by increasing interval length so sub-intervals are ready:

# Burst Balloons skeleton: dp[i][j] = max coins from bursting all in (i, j)
for length in range(2, n + 1):
    for i in range(0, n - length + 1):
        j = i + length
        for k in range(i + 1, j):            # k = the LAST balloon burst in (i,j)
            dp[i][j] = max(dp[i][j],
                           dp[i][k] + a[i]*a[k]*a[j] + dp[k][j])

The mind-bender that unlocks the family: think about the last decision in the interval, not the first — the last balloon burst, the outermost matrix multiplication — because that choice cleanly splits the interval into independent subproblems. O(n³) is normal here, and saying "interval DP, cubic, iterate by length" identifies you as someone who's met it before.

Family 6 — Bitmask DP (small n, subsets as states)

Tell: n ≤ ~20 (the constraint is the hint), and the state is "which items have I already used" — assignment problems, traveling salesman, minimum cost to visit all.

State: dp[mask] = best answer having used exactly the set of items encoded in mask's bits (bit i set = item i used). 2ⁿ states × O(n) transitions:

# Assign n tasks to n people, minimize total cost: dp over "tasks taken"
dp = [inf] * (1 << n)
dp[0] = 0
for mask in range(1 << n):
    person = bin(mask).count("1")            # next person to assign
    for task in range(n):
        if not mask & (1 << task):           # task still free
            new = mask | (1 << task)
            dp[new] = min(dp[new], dp[mask] + cost[person][task])

This family is where Level 0's binary becomes an algorithm tool: a 20-bit integer is a set, &/| are intersection/union. Rare in product-company loops, standard in competitive programming and quant interviews.

The decision tree (pin this)

Two sequences compared?            → LCS family
One sequence, order condition?     → LIS family
Budget/capacity + take-or-skip?    → knapsack (once = 0/1, reuse = unbounded)
2-D grid, directional movement?    → grid paths
Range splitting / "last action"?   → interval DP
n ≤ 20 and subsets matter?         → bitmask DP
None of the above?                 → back to first principles:
                                     define the state in one sentence
                                     (the fundamentals doc's recipe)

Common mistakes

• Skipping the state sentence. "dp[i][w] is the best value using the first i items with capacity w" — if you can't say it, the code is guesswork. Interviewers listen for exactly this sentence.
• Wrong loop direction in 1-D knapsack — upward iteration silently converts 0/1 into unbounded. Test with one item, capacity 2× its weight.
• LIS without "ending at i" — defining dp[i] as "best in the first i elements" breaks the recurrence; the locality comes from the ending-at anchor.
• Interval DP by start index instead of length — sub-intervals aren't computed yet; iterate lengths outward.
• Forcing DP onto greedy problems (intervals by end time!) or greedy onto DP problems (0/1 knapsack by ratio) — the greedy doc's fence runs both ways.
• Memorizing 40 problems instead of 6 recurrences — the families exist because variations are infinite and tells aren't.

Think it through

The whole page's thesis: spot the family under the disguise. Practice the single most common disguise — a problem that says nothing about "knapsack" but is exactly one. Reason before revealing.

// Java — Partition Equal Subset Sum
public boolean canPartition(int[] nums) {
    int total = 0;
    for (int num : nums) total += num;
    if (total % 2 != 0) return false;
    int target = total / 2;
    boolean[] dp = new boolean[target + 1];
    dp[0] = true;                        // empty subset sums to 0
    for (int num : nums) {
        for (int s = target; s >= num; s--) { // loop downward to use each num once
            dp[s] = dp[s] || dp[s - num];
        }
    }
    return dp[target];
}

// C++ — Partition Equal Subset Sum
#include <vector>
#include <numeric>

bool canPartition(const std::vector<int>& nums) {
    int total = std::accumulate(nums.begin(), nums.end(), 0);
    if (total % 2 != 0) return false;
    int target = total / 2;
    std::vector<bool> dp(target + 1, false);
    dp[0] = true;
    for (int num : nums) {
        for (int s = target; s >= num; s--) { // loop downward
            dp[s] = dp[s] || dp[s - num];
        }
    }
    return dp[target];
}

Interview perspective

Check yourself

Practice

1. One per family, from memory: Partition Equal Subset Sum (knapsack), LIS at O(n²) then via bisect (LIS), Edit Distance (LCS), Minimum Path Sum (grid), Palindrome Partitioning II or Burst Balloons (interval), and the task-assignment sketch above (bitmask).
2. The state drill: for five random DP problems from the problem bank, write only the state sentence and recurrence — no code. Five minutes each. This is the highest-ROI DP exercise that exists.
3. Direction proof: break 1-D knapsack on purpose (iterate upward), find the smallest input that exposes it, fix it, and explain why in one sentence.
4. Reduce: show that Longest Palindromic Subsequence = LCS(s, reverse(s)) — then say which family Longest Palindromic Substring belongs to instead, and why the difference matters (hint: expand-around-center, not DP).

Next: String Algorithms — pattern matching beyond what the naive scan can do.

Practice — climb the ladder

Foundations done — these are the named patterns interviews draw from: knapsack, partition, decision-with-cooldown, and interval DP.