Skip to content

Volume ITechnology

4.24.0 — 2-D Dynamic Programming: The Pattern ​

Recognition cue. The state needs two numbers. Almost always one of these three shapes:

shapethe two dimensionsexample
two sequencesa position in eachLCS, Edit Distance
a gridrow and columnUnique Paths
a position plus something elseindex and a budget, a count, or a stateknapsack, stock with cooldown

"Two strings" is the strongest cue in the whole chapter. The moment a problem gives you two sequences, draw a grid with one axis per string and ask what happens at the last character of each.

The two questions ​

1. What are the two cases at each cell? For two-sequence problems it is nearly always the characters match or they do not. Everything else follows.

2. What order fills the table? List what the recurrence reads. If it reads a smaller row and a smaller column, fill top to bottom, left to right. If it reads shorter ranges, fill by increasing length. Half of all 2-D DP bugs are reading a cell that has not been filled yet.

The two-sequence template ​

python
dp = [[0] * (n + 1) for _ in range(m + 1)]      # (1) (m+1) × (n+1), NOT m × n

for i in range(1, m + 1):  # (2)
    for j in range(1, n + 1):
        if a[i-1] == b[j-1]:  # (3)
            dp[i][j] = ...                       # (4) the match case
        else:  # (5)
            dp[i][j] = ...                       # the mismatch case

The template, line by line. (1) dp[i][j] is the answer for the first i items of a and the first j items of b. The extra row and column stand for the empty prefix. (2) Fill row by row, left to right, so every cell above, to the left and diagonally up-left is already done. (3) Compare the last item of each prefix. The - 1 turns a prefix length into a list position. (4) They match: usually build on the diagonal cell, dp[i-1][j-1]. (5) They differ: usually take the best of dropping the last item of a, dp[i-1][j], or of b, dp[i][j-1].

The +1 sizing and the −1 offsets go together. Row i means "the first i characters", so row 0 is the empty prefix and gives the base row for free. Sizing the table m × n forces special cases for the first row and column, and that is where the errors come from.

Only the two cases change between problems:

problemmatchmismatch
LCS1 + dp[i-1][j-1]max(dp[i-1][j], dp[i][j-1])
Edit Distancedp[i-1][j-1]1 + min(three)
Distinct Subsequencesdp[i-1][j-1] + dp[i-1][j]dp[i-1][j]
Longest Common Substring1 + dp[i-1][j-1]0 — must be contiguous

Interval DP: the other fill order ​

When the state is a range rather than two independent positions, the recurrence reads shorter ranges, so the loop is over length:

python
for length in range(2, n):
    for left in range(n - length):
        right = left + length
        for i in range(left + 1, right):        # the split point
            dp[left][right] = best(dp[left][i], dp[i][right], ...)

O(n^2) states and O(n) transitions gives O(n^3) — and n ≤ 300 in the constraints is the setter telling you that is the budget.

For interval problems, ask what happens LAST in the range, not first. Choosing the last event is what makes the two sides independent. That is the whole trick of 4.24.10 Burst Balloons.

Space optimisation, and its cost ​

If the recurrence reads only the previous row, two rows suffice — and often one, with the right loop direction:

  • Reading a smaller column from the previous row (dp[j-1] meaning the row above) → iterate backwards.
  • Reading a smaller column from the current row (dp[j-1] meaning this row) → iterate forwards.

The cost is always the same: you can no longer reconstruct the answer, only its value. Keep the full table whenever the problem asks which rather than how many or how much.

The eleven problems ​

#ProblemThe one insight
4.24.1Unique Paths ★Arrive from the left or from above
4.24.2Longest Common Subsequence ★The two-string grid template
4.24.3Stock with CooldownThe second dimension is a state, not a position
4.24.4Coin Change IICoins outside = combinations; inside = permutations
4.24.5Target SumAlgebra first: it reduces to a subset count
4.24.6Interleaving Strings3's position is i + j, so no third dimension
4.24.7Longest Increasing PathStrictly increasing = a DAG, so no visited set
4.24.8Distinct SubsequencesA match is optional, so the counts add
4.24.9Edit Distance ★Three operations = three neighbours
4.24.10Burst BalloonsChoose which balloon bursts last
4.24.11Regular Expression MatchingRead the pattern in x* pairs

★ marks the Blind 75 subset.

The traps on this pattern ​

Sizing the table m × n instead of (m+1) × (n+1). You lose the free base row and column.

Filling in the wrong order. List what the recurrence reads before writing the loops.

Rolling the array in the wrong direction. Backwards when reading a smaller column from the previous row; forwards when reading the current row.

Assuming a third dimension. Interleaving String looks 3-D and is not.

Treating * as an independent character in regex matching. It attaches to what precedes it.

What the interviewer will push on ​

"Why two dimensions?" Name what each axis is, in words.

"What are the two cases?" Match and mismatch, for every two-sequence problem.

"What order do you fill the table, and why?" The recurrence's dependencies.

"Can you reduce the space?" Two rows or one, with the direction justified — and say that reconstruction is lost.

"How would you recover the actual answer?" Keep the table and walk backwards, checking which predecessor produced each value.

One thing to volunteer: say the state definition, the two cases and the fill order out loud before writing anything. On 4.24.10 that habit is the difference between solving it and not.

Recall

  • Two sequences → a grid with one axis each. That is the strongest recognition cue in the chapter.
  • Size the table (m+1) × (n+1) so the empty prefixes give the base row and column for free.
  • Every two-sequence recurrence is the characters match or they do not. Only those two lines change between problems.
  • Fill order comes from what the recurrence reads. Smaller row and column → top-left to bottom-right. Shorter ranges → loop over length (interval DP, O(n^3)).
  • For interval problems, ask what happens last, not first — that is what makes the two sides independent.
  • Rolling direction: backwards when dp[j-1] must mean the previous row, forwards when it must mean the current one.
  • Space optimisation costs reconstruction. Keep the table when the question asks which.
  • The second dimension is not always a position — it can be a state (holding / sold / resting) or a budget.

Next: 4.24.1 Unique Paths — the simplest grid, and the place to build the fill-order habit.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet