parikshan

2-D Dynamic Programming

The core idea

The state is two indices, the table is a rectangle, and the recurrence reads dp[i][j] = f(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]). The geometry of the table is the entire problem: each cell's answer is built from cells one row up, one column left, or one diagonal step up-left. Once the table is filled, the answer lives in dp[m-1][n-1] (or at a boundary cell), and traceback recovers the actual choices.

Two ingredients matter:

  1. Two-string alignment: every problem about edit operations, common subsequences, regex matching, or sequence comparison fits here.
  2. Grid pathing: count or optimise paths through a grid with movement constraints.

When to reach for it

Trigger phrases:

  • "transform string A into string B"
  • "longest common ..." (subsequence, substring)
  • "edit distance / typo tolerance"
  • "number of paths from top-left to bottom-right"
  • "match this pattern against this string"

If you have two sequences and want a relationship between them, you almost certainly want 2-D DP.

How to approach

  1. State dp[i][j] in one English sentence ("min edits to transform A[0..i] into B[0..j]").
  2. Initialise the first row and first column. These are the trivial base cases (empty against prefix).
  3. Write three or four recurrence cases: characters match, characters differ, one string ran out, etc.
  4. Trace through a 3×3 example by hand, on paper. If your hand-trace disagrees with the code, the code is wrong.
  5. Notice if the row depends only on the previous row → collapse to two rows → O(n) space.

Enterprise scenarios

  • Stripe-style fuzzy matching: when a merchant types an SKU with a typo, edit-distance proposes the nearest valid one.
  • Git merge: the longest-common-subsequence DP is the engine behind every three-way merge you've ever resolved.
  • Salesforce data deduplication: comparing customer records across CRM imports; "John Smith, Acme Inc" vs "Jon Smith, Acme" needs edit distance.
  • Search engines: query spell-correction (Google's "did you mean ...") uses edit distance against a dictionary.
  • DNA assembly pipelines (Illumina, Oxford Nanopore): sequence alignment is 2-D DP at industrial scale.
  • Compiler tools: diff utilities (diff, git diff, IDE merge conflict resolvers).
  • CI/CD platforms: dependency-resolution between manifests when two branches change package.json.

In the AI-integrated workspace

2-D DP is exactly the kind of problem AI agents will gladly generate wrong code that passes the small test case. The off-by-one between "the prefix of length i" and "index i" is the single most common mistake; it produces results that are correct on small inputs and shift by one on inputs of length 10+.

In parikshan's loop, after you read this primer and your AI training assistant (the /api/training/improve "Explain" button) produces a solution, you do not accept it blindly. You ask the assistant to fill out a 4×4 table by hand for a worked example, and you cross-check. If the table is consistent with the code's output, the recurrence is right. If not, you ask the assistant to revise. This back-and-forth is the integrated practice loop: read concept, AI codes, you audit, you direct the revision, you submit.

When you ship 2-D DP code in production (string-similarity matching at scale), profile the memory. Two-row optimisation matters: a 100k × 100k DP table is 10 GB; a two-row variant is 800 KB.

Problems in this cluster

Medium: unique-paths, longest-common-subsequence. Hard: edit-distance.

Start with unique-paths. Pure counting on a grid, no character matching, the cleanest 2-D DP imaginable.