DP Patterns Explained: Knapsack, LIS, Edit Distance & Grid Paths

Here is the open secret about DP interviews: they feel infinite, and they aren't. The questions that actually get asked cluster into a handful of families, and within a family the state, the recurrence shape, even the table dimensions repeat. Learn the family heads properly, and a "new" DP problem becomes two questions: which family is this, and what got renamed?

This lesson builds the four families that cover most placement and product-company DP — knapsack, sequences (LIS), two strings (LCS / edit distance) and grid paths — each derived with lesson 7's ritual (state → last decision → base cases) and each traced by hand once, because a table you have filled yourself is a table you can rebuild under pressure.

Family 1: 0/1 knapsack

The setup where greedy failed: items with weight and value, a capacity, each item taken whole or not at all. Run the ritual.

State. One index isn't enough — knowing "best value with capacity 6" doesn't say which items are still available. The state needs both dimensions: dp[i][w] = best value using only the FIRST i items, within capacity w.

Last decision. Item i: take it or skip it. Skip → dp[i−1][w]. Take (if it fits) → its value + the best the previous items manage in the REMAINING capacity: dp[i−1][w − wt] + val. Max of the two:

def knapsack(weights, values, cap):
    n = len(weights)
    dp = [[0] * (cap + 1) for _ in range(n + 1)]   # row 0: no items -> 0
    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 it?
                take = dp[i - 1][w - weights[i - 1]] + values[i - 1]
                dp[i][w] = max(dp[i][w], take)
    return dp[n][cap]

# A(1kg, Rs15), B(3kg, Rs50), C(4kg, Rs60), capacity 6
print(knapsack([1, 3, 4], [15, 50, 60], 6))

75

Dry run: the knapsack that beat greedy

columns w = 0..6;  each row adds one item

no items:  0   0   0   0   0   0   0
A(1,15):   0  15  15  15  15  15  15
B(3,50):   0  15  15  50  65  65  65
           (w=4: take B -> 50 + dp[A][1]=15 -> 65)
C(4,60):   0  15  15  50  65  75  75
           (w=5: take C -> 60 + dp[B][1]=15 = 75 beats skip 65)
           (w=6: take C -> 60 + dp[B][2]=15 = 75 vs skip 65 -> 75)

answer 75 = A + C (5kg of 6). Ratio-greedy would take B first
and land on 65 - the table quietly out-negotiated it.

The detail that defines the family: the take-option reads the previous row — dp[i−1][...] — because item i, once taken, is gone. Hold that thought for exactly one section.

One index changes everything: unbounded knapsack

What if items are reusable — take item i as many times as you like? After taking item i, it's... still available. So the take-option should consult the same row: dp[i][w − wt] + val. One index, i−1 → i, and 0/1 knapsack becomes unbounded knapsack — whose most famous member you already solved in lesson 7: coin change (coins are items, amount is capacity, every coin infinitely reusable).

Same-row take = reuse allowed; previous-row take = each item once. Interviewers flip this switch deliberately; now it can't catch you.

Family 2: longest increasing subsequence

First, the vocabulary trap that fails candidates before any algorithm: a subsequence keeps order but may SKIP elements; a subarray may not. LIS of [10, 9, 2, 5, 3, 7, 101, 18]:

State — and here's the family's signature move: dp[i] = length of the longest increasing subsequence ENDING exactly at index i. Why "ending at"? Because without that anchor, "can I extend this subsequence with arr[i]?" isn't answerable — you must know what its last element is, and anchoring at i makes the last element arr[i].

def lis(arr):
    n = len(arr)
    dp = [1] * n                # every element alone: length 1
    for i in range(n):
        for j in range(i):      # who could I extend?
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)              # best can END anywhere -> max over all

print(lis([10, 9, 2, 5, 3, 7, 101, 18]))

4

dp fills as [1, 1, 1, 2, 2, 3, 4, 4] → answer 4 (e.g. 2, 5, 7, 101 — verify: increasing ✓). Two graded details: the answer is max over the whole table, not dp[n−1] (the best subsequence can end anywhere), and the O(n²) here is the expected answer — naming the O(n log n) patience-sorting upgrade is the bonus point, deriving it is not required.

Family 3: two strings — LCS and edit distance

Anything comparing two sequences — diff tools, spell-check, plagiarism checkers — lives on a 2-D table indexed by prefixes of each string. Family head: longest common subsequence. State: dp[i][j] = LCS length of A's first i characters and B's first j. Last decision — look at the two last characters:

def lcs(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]   # row/col 0 = empty prefix
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1        # match: diagonal + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])   # drop one side
    return dp[m][n]

print(lcs("ABCBDAB", "BDCABA"))

4

The cell logic in words: matching last characters certainly end some best common subsequence — pair them, add 1 to the both-prefixes- shorter diagonal. Mismatched last characters can't both survive — drop one or the other, take the better, no +1. (Adding 1 on the mismatch branch is THE classic LCS bug.)

Edit distance ("cat" → "cut": 1 replace) is the same table with three options per mismatch — 1 + min(delete, insert, replace) = 1 + min(up, left, diagonal) — and a free diagonal copy on match. Master the LCS cell and edit distance is a ten-minute variation.

Family 4: grid paths

Count paths from top-left to bottom-right, moving only right or down. Last decision writes itself: the final step into (r, c) came from above or from the left — disjoint families, so ADD:

def unique_paths(m, n):
    dp = [[1] * n for _ in range(m)]     # edges: only one way along them
    for r in range(1, m):
        for c in range(1, n):
            dp[r][c] = dp[r - 1][c] + dp[r][c - 1]
    return dp[m - 1][n - 1]

print(unique_paths(3, 3))

6

The family flexes without new machinery: an obstacle zeroes its cell and the sums route around it automatically; minimum path sum swaps + for min plus the cell's own cost. The grid IS the state space — the friendliest family for learning to think in tables, and it's in your Practice Zone with an obstacle traced.

Same problem, different costume

Now the skill this lesson exists for. Read this problem fresh: "Given numbers, can you split them into two groups with equal sums?"

Pause. Which family? Rephrase: does some SUBSET of the numbers hit target sum total/2? Items chosen-or-not against a capacity... 0/1 knapsack — values ignored, feasibility instead of max. "Count subsets summing to K" — knapsack, counting variant. "Minimum coins for an amount" — unbounded knapsack. "Longest palindromic subsequence" — LCS of the string with its own reverse.

Most "new" DP problems are these four families reskinned — name the family before writing anything. The stories change (thieves, partitions, typos); the states don't.

🎯 Selection-round radar: reported frequencies put coin change, LCS/edit distance, LIS, and partition-equal-subset-sum at the top of product-company DP lists. All four are family heads or one-step variants — this lesson is built from exactly them.

What if...?

What if I need the actual answer (the items, the subsequence), not just the number? Backtrack through the filled table: from the final cell, ask which option produced its value (did the diagonal fire? did I take item i?), record the decision, step to the source cell. No new table, O(path) extra — and it's the follow-up about half the time.

What if W (capacity) is huge — 10⁹? O(n·W) is pseudo-polynomial — polynomial in W's numeric value, not its digit count — and a 10⁹-wide table is impossible. Huge capacities are a signal the intended solution is something else entirely. Knowing the term "pseudo-polynomial" here is a quiet flex.

What if the strings are enormous (LCS on files)? The length needs only two rows (the recurrence reads row i−1) — lesson 7's space trick. Recovering the actual subsequence with limited memory is harder (Hirschberg's trick exists); name it, don't derive it.

What if the boundary row confuses me? Row and column 0 mean "empty prefix" / "zero items" — answers 0 by definition. That +1 offset is what keeps dp[i][j] meaning "first i, first j" with no index gymnastics; skipping it is the off-by-one factory.

Common mistakes

• Confusing subsequence with subarray — it decides LIS vs Kadane, and interviewers check deliberately.
• Reading the same row in 0/1 knapsack's take-option — silently allows reuse (you've built unbounded by accident).
• +1 on LCS's mismatch branch.
• Returning dp[n−1] for LIS instead of max(dp).
• Skipping the zero boundary row/column in 2-D tables.
• Coding before naming the family — recognition is where the marks are.

The family recognition checklist

choose items? budget/target? each at most once?  -> 0/1 knapsack
  ...items reusable?                             -> unbounded (coin change)
best subsequence WITHIN one array?               -> LIS family
TWO strings/sequences compared?                  -> LCS / edit distance
move through a grid, count/min/max paths?        -> grid family
linear sequence + adjacent constraint?           -> house robber style

Six lines that route most DP interviews. When none fits, fall back to the ritual: state meaning → last decision → base cases → fill order. The families are just cached outputs of that ritual.

Quick revision

Space note: every 2-D family here reads only the previous row (or diagonal) — two rows suffice, per lesson 7's rule.

One thing to remember

DP interviews are four families in costume — knapsack, LIS, two-strings, grid. Name the family first; the state and table come with the name.

Practice Zone — PYQs from real selection rounds

Six MCQs, then three tables filled by hand: the knapsack that beat greedy, LCS with the diagonal rule visible, and grid paths around an obstacle.

Q1DP patternseasy

In 0/1 knapsack, the state dp[i][w] means:

Asked in

aThe weight of item ibThe maximum value achievable using only the first i items within capacity wcWhether item i fits in the bagdThe number of items that weigh w

Q2DP patternsmedium

Longest Common Subsequence of "ABCBDAB" and "BDCABA" — the recurrence when characters MATCH is:

Asked in

adp[i][j] = dp[i−1][j−1] + 1 — extend the LCS of both prefixes without their last charactersbdp[i][j] = max(dp[i−1][j], dp[i][j−1]) + 1cdp[i][j] = dp[i][j] + 1ddp[i][j] = 2

Q3DP patternsmedium

Longest Increasing Subsequence of [10, 9, 2, 5, 3, 7, 101, 18] has length:

Asked in

a3b4 — e.g. 2, 3, 7, 18 (or 2, 5, 7, 101)c5d2

Q4DP patternsmedium

Edit distance (convert "cat" to "cut") counts minimum insert/delete/replace operations. The answer is 1 because:

Asked in

aOne REPLACE (a → u) suffices; the DP's three options per cell correspond exactly to insert, delete, replacebDelete 'a' then insert 'u' is the only way — distance 2cThe strings have equal length, so the distance is 0dIt equals the number of shared letters

Q5DP patternsmedium

Unique paths in an m×n grid (move right/down only): dp[r][c] = dp[r−1][c] + dp[r][c−1] because:

Asked in

aEvery cell is reached either from above or from the left, and those route sets are disjointbThe grid is symmetriccDiagonal moves count twicedIt is the area of the grid

Q6DP patternshard

You see a new problem: "count the ways to make sum S using given numbers, each usable unlimited times". Which pattern family is this?

Asked in

aLIS — it's about sequencesbUnbounded knapsack / coin-change family — items with reuse, target capacity, count or optimise over choicescEdit distance — two sequences compareddGrid paths — it's about counting

Hands-on tasks:

FAQ

Four families, one ritual. Next, we leave sequences for networks — exploring graphs level by level and depth by depth — Lesson 9: BFS & DFS →