2D Dynamic Programming

When Does a Problem Need 2D DP?

A problem needs 2D DP when the state cannot be captured by a single index. Two indices are required.

SIGNALS THAT YOU NEED 2D DP:
  "Two strings or sequences" → dp[i][j] = answer for s1[0..i-1] and s2[0..j-1]
  "Grid movement"            → dp[i][j] = answer to reach cell (i,j)
  "Interval [i..j]"         → dp[i][j] = answer for the sub-array from i to j
  "Item i with remaining w"  → dp[i][w] = answer using i items with capacity w

2D STATE SHAPES:
  dp[i][j] where i,j are both POSITIONS in same array (interval DP)
  dp[i][j] where i is position in s1, j in s2 (two-string DP)
  dp[i][j] where i is row, j is column (grid DP)
  dp[i][w] where i is item index, w is capacity (knapsack-style)

FILL ORDERS BY SHAPE:
  Grid DP:       Row by row, left to right (i outer, j inner)
  Two-string DP: Row by row, left to right (same)
  Interval DP:   By increasing interval LENGTH (non-obvious)

Pattern 1: Grid DP

Unique Paths

STATE:   dp[i][j] = number of paths to reach cell (i,j)
RECUR:   dp[i][j] = dp[i-1][j] + dp[i][j-1]  (from above or from left)
BASE:    dp[0][j] = 1 for all j  (first row: only rightward moves)
         dp[i][0] = 1 for all i  (first col: only downward moves)
FILL:    Row by row, left to right
ANSWER:  dp[m-1][n-1]

Table for 3×4 grid:
      j=0  j=1  j=2  j=3
i=0 [  1,   1,   1,   1 ]
i=1 [  1,   2,   3,   4 ]
i=2 [  1,   3,   6,  10 ]

dp[1][1] = dp[0][1]+dp[1][0] = 1+1 = 2
dp[2][3] = dp[1][3]+dp[2][2] = 4+6 = 10

Minimum Path Sum

STATE:   dp[i][j] = min cost to reach cell (i,j)
RECUR:   dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
BASE:    dp[0][0] = grid[0][0]
         dp[0][j] = dp[0][j-1] + grid[0][j]  (first row: only right)
         dp[i][0] = dp[i-1][0] + grid[i][0]  (first col: only down)
FILL:    Row by row, left to right
ANSWER:  dp[m-1][n-1]

Grid:             dp table:
  1  3  1           1  4  5
  1  5  1    →      2  7  6
  4  2  1           6  8  7

dp[1][1]=grid[1][1]+min(dp[0][1],dp[1][0])=5+min(4,2)=7
dp[2][3]=grid[2][2]+min(dp[1][2],dp[2][1])=1+min(6,8)=7
Answer = 7 (path: 1→3→1→1→1 = 7, but 1→1→5→1→... no)
         Check: 1→1→1→1→1 = path 1→right? No.
         Path: (0,0)→(1,0)→(2,0)→(2,1)→(2,2) = 1+1+4+2+1=9? No.
         Path: (0,0)→(0,1)→(0,2)→(1,2)→(2,2) = 1+3+1+1+1=7 ✓

Unique Paths II (With Obstacles)

Same as Unique Paths but obstacle cells = 0 paths (dp[i][j] = 0).

RECUR:   if grid[i][j] == 1 (obstacle): dp[i][j] = 0
         else: dp[i][j] = dp[i-1][j] + dp[i][j-1]

KEY: Obstacles block all paths through that cell.
An obstacle in first row/col zeros out ALL subsequent cells in that row/col.

Pattern 2: Two-String DP

Longest Common Subsequence (LCS)

STATE:   dp[i][j] = LCS length of s1[0..i-1] and s2[0..j-1]
RECUR:   if s1[i-1]==s2[j-1]: dp[i][j] = 1 + dp[i-1][j-1]  (match: extend)
         else:                 dp[i][j] = max(dp[i-1][j],    (skip s1[i-1])
                                              dp[i][j-1])    (skip s2[j-1])
BASE:    dp[0][j] = 0 for all j  (empty s1: LCS = 0)
         dp[i][0] = 0 for all i  (empty s2: LCS = 0)
FILL:    Row by row, left to right
ANSWER:  dp[m][n]

Table for s1="abcde", s2="ace":

      ""  a  c  e
   "" [0, 0, 0, 0]
   a  [0, 1, 1, 1]
   b  [0, 1, 1, 1]
   c  [0, 1, 2, 2]
   d  [0, 1, 2, 2]
   e  [0, 1, 2, 3]

LCS = 3 (subsequence "ace") ✓

Edit Distance (Levenshtein Distance)

STATE:   dp[i][j] = min edits to transform s1[0..i-1] into s2[0..j-1]
         Operations: insert, delete, replace — each costs 1

RECUR:   if s1[i-1]==s2[j-1]:  dp[i][j] = dp[i-1][j-1]     (no cost: match)
         else:                  dp[i][j] = 1 + min(
           dp[i-1][j],                                       (delete s1[i-1])
           dp[i][j-1],                                       (insert s2[j-1])
           dp[i-1][j-1])                                     (replace)

BASE:    dp[0][j] = j  (transform "" into s2[0..j-1]: j inserts)
         dp[i][0] = i  (transform s1[0..i-1] into "": i deletes)
FILL:    Row by row, left to right
ANSWER:  dp[m][n]

Table for s1="horse", s2="ros":

      ""  r  o  s
   "" [0, 1, 2, 3]
   h  [1, 1, 2, 3]
   o  [2, 2, 1, 2]
   r  [3, 2, 2, 2]
   s  [4, 3, 3, 2]
   e  [5, 4, 4, 3]

Edit distance = 3 (horse→rorse→rose→ros) ✓

Pattern 3: Interval DP

Interval DP answers questions about sub-arrays or sub-strings of form [i..j].

KEY INSIGHT:
  dp[i][j] = answer for the interval [i, j]
  Depends on SHORTER intervals: dp[i][k] and dp[k+1][j] for some split k

FILL ORDER — by increasing interval length:
  for length in 2..n:             ← interval length
    for i in 0..n-length:         ← start of interval
      j = i + length - 1          ← end of interval
      for k in i..j-1:            ← split point
        dp[i][j] = combine(dp[i][k], dp[k+1][j])

BASE: dp[i][i] = answer for single element (length 1)

Burst Balloons

PROBLEM: Burst all balloons, earn nums[left]*nums[i]*nums[right] when bursting i.
         Maximise total coins.

TRICK: Think BACKWARDS — which balloon is burst LAST in interval [i,j]?

STATE:   dp[i][j] = max coins from bursting ALL balloons in (i,j)
         (i and j are kept as boundaries, not burst)
RECUR:   dp[i][j] = max over k in (i,j):
           nums[i] * nums[k] * nums[j] + dp[i][k] + dp[k][j]
         k = the LAST balloon burst in (i,j)

BASE:    dp[i][j] = 0 when interval is empty (j = i+1)
         Pad array: nums = [1] + nums + [1] (virtual boundary balloons)

For nums = [3,1,5,8], padded = [1,3,1,5,8,1]:

Interval lengths 2,3,4,5,6 filled in order.
dp[0][5] = max total coins = 167 ✓

Matrix Chain Multiplication

PROBLEM: Given matrix dimensions, find optimal parenthesisation
         to minimise total multiplications.

STATE:   dp[i][j] = min multiplications to compute product A_i * ... * A_j
RECUR:   dp[i][j] = min over k in [i,j-1]:
           dp[i][k] + dp[k+1][j] + dims[i-1]*dims[k]*dims[j]
           (cost of left chain) + (cost of right chain) + (cost of final multiply)

BASE:    dp[i][i] = 0  (single matrix: no multiplications)
FILL:    By increasing interval length
ANSWER:  dp[1][n]  (chain of n matrices)

dims = [10, 30, 5, 60]:
  Matrices: A1(10×30), A2(30×5), A3(5×60)

  dp[1][1]=0, dp[2][2]=0, dp[3][3]=0  (base)

  Length 2:
    dp[1][2]: k=1: 0+0+10*30*5=1500. dp[1][2]=1500
    dp[2][3]: k=2: 0+0+30*5*60=9000. dp[2][3]=9000

  Length 3:
    dp[1][3]:
      k=1: dp[1][1]+dp[2][3]+10*30*60 = 0+9000+18000 = 27000
      k=2: dp[1][2]+dp[3][3]+10*5*60  = 1500+0+3000  = 4500 ← min
    dp[1][3] = 4500

Answer: 4500 (parenthesise as (A1*A2)*A3) ✓

Complete Implementations

Output:
Unique Paths(3,4):   10
Min Path Sum:         7
LCS(abcde,ace):       3
Edit Distance(horse,ros): 3
Burst Balloons:     167
Matrix Chain:       4500

Space Optimisation for 2D DP

Grid DP: O(m×n) → O(n)

For Unique Paths and Min Path Sum:
dp[i][j] only needs dp[i-1][j] (above) and dp[i][j-1] (left in same row).

Use single 1D array — it holds previous row initially, then gets updated left-to-right:

  prev = [1]*n   ← represents first row

  for i in 1..m-1:
    curr = [1] + [0]*(n-1)
    for j in 1..n-1:
      curr[j] = prev[j] + curr[j-1]
    prev = curr

  return prev[n-1]

Unique Paths: O(m×n) → O(n)
Min Path Sum: O(m×n) → O(n)

Two-String DP: O(m×n) → O(n)

For LCS and Edit Distance:
dp[i][j] needs dp[i-1][j-1], dp[i-1][j], dp[i][j-1].
Only the previous row is needed.

LCS with rolling row:
  dp = [0]*(n+1)
  for i in 1..m:
    new_dp = [0]*(n+1)
    for j in 1..n:
      if s1[i-1]==s2[j-1]: new_dp[j] = 1 + dp[j-1]  ← diagonal: dp[i-1][j-1]
      else: new_dp[j] = max(dp[j], new_dp[j-1])       ← dp[i-1][j] and dp[i][j-1]
    dp = new_dp
  return dp[n]

LCS: O(m×n) → O(n)
Edit Distance: O(m×n) → O(n) (same rolling row pattern)

Interval DP Fill Order Visualised

Interval DP fills by LENGTH, not by row:

For array of size 4: indices 0,1,2,3

Step 1 — Length 1 (base cases): fill diagonal
  dp[0][0]=0, dp[1][1]=0, dp[2][2]=0, dp[3][3]=0

Step 2 — Length 2: adjacent pairs
  dp[0][1], dp[1][2], dp[2][3]

Step 3 — Length 3:
  dp[0][2], dp[1][3]

Step 4 — Length 4 (answer):
  dp[0][3]

TABLE FILLED IN ORDER:
      j=0  j=1  j=2  j=3
i=0 [ ①,   ②,   ③,   ④ ]
i=1 [  _,   ①,   ②,   ③ ]
i=2 [  _,    _,   ①,   ② ]
i=3 [  _,    _,    _,   ① ]

Fill diagonal first, then upper-right triangle by increasing offset.
Only the upper triangle (i ≤ j) is filled (intervals [i,j] only valid when i≤j).

Pattern Summary

PATTERN              STATE           FILL ORDER          EXAMPLE
─────────────────────────────────────────────────────────────────────
Grid movement        dp[i][j]        Row by row          Unique Paths
                     = answer        (i outer, j inner)  Min Path Sum
                     to reach (i,j)

Two strings          dp[i][j]        Row by row          LCS
                     = answer for    (i outer, j inner)  Edit Distance
                     s1[:i], s2[:j]                      Longest Common
                                                          Substring

Interval             dp[i][j]        By interval length  Burst Balloons
                     = answer for    (len outer, i inner, Matrix Chain
                     subarray [i,j]  j = i+len-1)        Palindrome Partition

Item + capacity      dp[i][w]        Row by row          0/1 Knapsack
                     = answer using  (i outer, w inner)  Unbounded Knapsack
                     items[0..i-1]
                     with capacity w

Complexity Summary

Common Mistakes

Edit Distance: base case dp[i][0] = i, not dp[i][0] = 0. dp[i][0] means "transform s1[0..i-1] into an empty string" — that requires i deletions. dp[0][j] = j means "transform empty string into s2[0..j-1]" — j insertions. Initialising these to 0 breaks the recurrence for the first row and column.

Interval DP: filling by row instead of by interval length. If you fill dp[1][3] before dp[2][3], the recurrence dp[1][3] = min over k of dp[1][k]+dp[k+1][3] references dp[2][3] which is still 0 — wrong. Always fill shorter intervals before longer ones.

Burst Balloons: not padding with boundary 1s. When balloon k is the last burst in interval (i,j), it earns nums[i]*nums[k]*nums[j] — but i and j are boundaries, not burst in this interval. Padding with [1]+nums+[1] provides the virtual boundaries without special-casing.

LCS vs Longest Common Substring confusion. LCS (subsequence) allows skipping characters — dp[i][j] = max(dp[i-1][j], dp[i][j-1]) when no match. Longest Common Substring (contiguous) requires: dp[i][j] = dp[i-1][j-1]+1 if match, else 0. The result is max(dp[i][j]) over all cells, not dp[m][n].

2D array allocation in Java: new int[m+1][n+1] vs new int[m][n]. For LCS and Edit Distance, use [m+1][n+1] to accommodate empty string base cases at index 0. For grid problems (Unique Paths), use [m][n] since the grid indices start at 0. Mixing these up causes index-out-of-bounds or wrong base case positions.

Interview Questions

Q: Edit Distance — what do the three recurrence cases (dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) each correspond to?

dp[i-1][j] + 1 = delete operation: remove s1[i-1], then solve the remaining problem of transforming s1[0..i-2] into s2[0..j-1]. dp[i][j-1] + 1 = insert operation: insert s2[j-1] at the end of s1[0..i-1], then the remaining problem is transforming s1[0..i-1] into s2[0..j-2]. dp[i-1][j-1] + 1 = replace operation: replace s1[i-1] with s2[j-1], then solve the remaining problem of transforming s1[0..i-2] into s2[0..j-2].

Q: Why is Burst Balloons solved by thinking about which balloon is burst LAST rather than first?

If we think about which balloon is burst first at position k in interval [i,j], the coins are nums[left]*nums[k]*nums[right] — but left and right depend on which adjacent balloons still exist, which changes as other balloons burst. This creates complicated dependencies. Thinking about the last balloon k burst in interval (i,j): since k is last, the sub-intervals (i,k) and (k,j) are fully burst first, and k sees boundaries i and j (which are not burst in this interval). The cost is a clean formula: nums[i]*nums[k]*nums[j] + dp[i][k] + dp[k][j].

Q: When can a 2D DP table be space-optimised to O(n), and when can it not?

Space reduction from O(m×n) to O(n) is possible when computing dp[i][j] only needs the current row (being built) and the previous row (already complete). This applies to grid DP (Unique Paths, Min Path Sum), two-string DP (LCS, Edit Distance), and row-by-row knapsack. It does NOT apply to interval DP (Burst Balloons, Matrix Chain) because dp[i][j] depends on dp[i][k] and dp[k+1][j] — references to multiple rows simultaneously, not just the adjacent previous row.

Summary

2D DP captures state using two indices: row+column for grids, position-in-each-string for two-string problems, or interval-start+interval-end for interval DP.

Four patterns:

Space optimisation:

• ›Grid / two-string: O(m×n) → O(n) using rolling row
• ›Interval DP: cannot reduce below O(n²) — needs full upper triangle

The non-obvious insight for interval DP: fill by interval length, not by row. Dependencies are shorter intervals, not previous rows.

In the next topic you will explore Knapsack Pattern — the 0/1 knapsack, unbounded knapsack, and subset sum with all their variations.