Data Structures & Algorithms2D DP Problems — Grid Paths & LCS

2D Dynamic Programming — Grid Paths & Longest Common Subsequence

LevelIntermediate

Duration75 mins

Topic2D DP Problems — Grid Paths & LCS

3 / 4

State: Two Indices

The Art of State Design in 2D DP

We've solved grid paths and LCS—two problems that require 2D DP tables. But why two dimensions? What made us choose (row, column) for grids and (i, j) for LCS? Could we have solved these with 1D state? Adding a third index?

These questions touch on the art of DP state design—arguably the hardest part of dynamic programming. The algorithm itself (memoization or tabulation) is mechanical once you define the right state. But defining that state requires insight.

This page makes state design systematic. We'll develop a framework for recognizing when 2D state is necessary and how to choose the right indices. Master this, and you'll be able to tackle novel DP problems with confidence.

What You Will Learn

By the end of this page, you will understand: (1) what 'state' means in DP and why it matters, (2) when a problem requires two indices, (3) how to identify what those indices should represent, and (4) common patterns for 2D state across different problem types.

What Is State in Dynamic Programming?

Definition:

In dynamic programming, state is the minimal information needed to describe a subproblem uniquely. The state determines:

What subproblem we're solving
What the answer to that subproblem is
How larger subproblems depend on smaller ones

The State Space:

The collection of all possible states forms the state space. The size of this space determines the time and space complexity of our DP solution:

1D DP: State is a single variable → O(n) states
2D DP: State is a pair of variables → O(n×m) states
3D DP: Three variables → O(n×m×k) states

The DP table is just a concrete representation of the state space, where each cell stores the answer for one state.

State Examples Across Problem Types
Problem	State	Meaning	Table Size
Fibonacci	n	n-th Fibonacci number	O(n)
Climbing Stairs	step	Ways to reach step i	O(n)
Grid Paths	(row, col)	Ways to reach cell (row, col)	O(m×n)
LCS	(i, j)	LCS of X[0..i-1] and Y[0..j-1]	O(m×n)
0/1 Knapsack	(item, capacity)	Max value with items 0..i and capacity c	O(n×W)
Matrix Chain	(i, j)	Min cost to multiply matrices i..j	O(n²)

State = Subproblem Identifier

Think of state as a unique identifier for a subproblem. If two recursive calls have the same state, they're solving the same subproblem—which is exactly when memoization helps. The state must capture everything that affects the answer, but nothing more (to avoid redundant dimensions).

When Do We Need Two Indices?

Not every problem needs 2D state. Here are the key indicators that suggest two indices are necessary:

Signal 1: Two Independent Sequences or Dimensions

When the problem involves two separate sequences (strings, arrays) that we're comparing, aligning, or processing together, we typically need an index for each.

Examples:

LCS: comparing two strings → indices (i, j) for positions in each
Edit Distance: transforming one string to another → same structure
Interleaving Strings: combining two strings → track position in each

Signal 2: Grid or Matrix Structure

Problems defined on 2D grids naturally need row and column indices.

Examples:

Grid paths, minimum path sum, dungeon game
Matrix chain multiplication (though indexed by subrange)

Signal 3: Range or Interval Processing

When we need to consider contiguous ranges of a single sequence, we use two indices for the start and end of the range.

Examples:

Matrix chain multiplication: dp[i][j] = min cost for matrices i to j
Palindrome partitioning: dp[i][j] = whether s[i..j] is palindrome
Burst balloons: dp[i][j] = max coins from bursting i to j

Converting Mermaid diagram...

The Key Test:

Ask yourself: Can I describe a subproblem completely with a single number?

Fibonacci: Yes, just need n. → 1D DP
LCS: No, need position in each string. → 2D DP
Grid paths: No, need row and column. → 2D DP
House robber: Yes, just need index up to which we've decided. → 1D DP
Knapsack: No, need item index AND remaining capacity. → 2D DP

If one number isn't enough to uniquely identify subproblems, you need more dimensions.

Minimality Matters

The goal is the minimal state that uniquely identifies subproblems. Using more dimensions than necessary wastes time and space. Using fewer makes the recurrence impossible. Finding the right balance is the art of DP.

Common 2D State Patterns

Through experience, certain 2D state patterns recur. Recognizing these accelerates problem-solving:

Pattern 1: Position-Position (Two Sequences)

State: dp[i][j] = result for X[0..i-1] combined with Y[0..j-1]

Used in: LCS, edit distance, interleaving strings, regular expression matching.

Pattern 2: Position-Position (Grid)

State: dp[row][col] = result for reaching/leaving cell (row, col)

Used in: Unique paths, minimum path sum, dungeon game, cherry pickup.

Pattern 3: Range (Start-End)

State: dp[i][j] = result for subarray/substring from index i to j

Used in: Matrix chain multiplication, burst balloons, palindrome-related problems.

Pattern 4: Index-Capacity (Knapsack-style)

State: dp[i][c] = result considering items 0..i-1 with capacity/budget c

Used in: 0/1 knapsack, coin change (2D variant), subset sum with targets.

state_patterns_examples.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
# ============================================================
# Pattern 1: Position-Position (Two Sequences)
# ============================================================
def edit_distance(X: str, Y: str) -> int:
    """
    State: dp[i][j] = min edits to transform X[0..i-1] to Y[0..j-1]
    
    Two sequences → two indices (i for X, j for Y)
    """
    m, n = len(X), len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Base cases: transforming to/from empty string
    for i in range(m + 1):
        dp[i][0] = i  # Delete all characters from X
    for j in range(n + 1):
        dp[0][j] = j  # Insert all characters of Y
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i-1] == Y[j-1]:
                dp[i][j] = dp[i-1][j-1]  # No operation needed
            else:
                dp[i][j] = 1 + min(
                    dp[i-1][j],    # Delete from X
                    dp[i][j-1],    # Insert into X
                    dp[i-1][j-1]   # Replace in X
                )
    
    return dp[m][n]
 
 
# ============================================================
# Pattern 2: Position-Position (Grid)
# ============================================================
def min_path_sum(grid: list[list[int]]) -> int:
    """
    State: dp[row][col] = min sum to reach (row, col) from (0, 0)
    
    Grid → two indices (row, column)
    """
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]
    
    # Base case: starting cell
    dp[0][0] = grid[0][0]
    
    # First row: can only come from left
    for j in range(1, n):
        dp[0][j] = dp[0][j-1] + grid[0][j]
    
    # First column: can only come from above
    for i in range(1, m):
        dp[i][0] = dp[i-1][0] + grid[i][0]
    
    # Fill rest
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
    
    return dp[m-1][n-1]
 
 
# ============================================================
# Pattern 3: Range (Start-End)
# ============================================================
def is_palindrome_range(s: str) -> list[list[bool]]:
    """
    State: dp[i][j] = True if s[i..j] is a palindrome
    
    Range → two indices (start, end of substring)
    """
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    
    # Base case: single characters are palindromes
    for i in range(n):
        dp[i][i] = True
    
    # Base case: two characters
    for i in range(n - 1):
        dp[i][i+1] = (s[i] == s[i+1])
    
    # Fill for lengths 3 and up
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            # s[i..j] is palindrome if ends match and middle is palindrome
            dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]
    
    return dp
 
 
# ============================================================
# Pattern 4: Index-Capacity (Knapsack-style)
# ============================================================
def knapsack_01(weights: list[int], values: list[int], capacity: int) -> int:
    """
    State: dp[i][c] = max value using items 0..i-1 with capacity c
    
    Items + constraint → two indices (item index, remaining capacity)
    """
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for c in range(capacity + 1):
            # Don't take item i-1
            dp[i][c] = dp[i-1][c]
            
            # Take item i-1 if it fits
            if weights[i-1] <= c:
                dp[i][c] = max(
                    dp[i][c],
                    values[i-1] + dp[i-1][c - weights[i-1]]
                )
    
    return dp[n][capacity]
 
 
# Examples
print(f"Edit distance 'kitten' → 'sitting': {edit_distance('kitten', 'sitting')}")
print(f"Min path sum: {min_path_sum([[1,3,1],[1,5,1],[4,2,1]])}")
print(f"Knapsack: {knapsack_01([2,3,4,5], [3,4,5,6], 5)}")

Pattern Recognition = Speed

When you encounter a new problem, quickly check: Does it involve two sequences? A grid? Ranges? An item-capacity trade-off? Matching to a pattern immediately suggests the state structure, saving significant thinking time.

Deriving State from Problem Structure

When patterns don't immediately apply, we need a systematic approach to derive state. Here's a framework:

Step 1: Identify What Changes

Ask: As I solve this problem recursively, what information changes between recursive calls?

In grid paths: my current position (row, col) changes
In LCS: how much of each string I've processed (i, j) changes
In knapsack: which items I've considered (i) and remaining capacity (c) change

Each changing piece of information is a candidate for a state dimension.

Step 2: Determine What Affects the Answer

Not everything that changes matters. Ask: Does knowing X affect my optimal decision or answer?

In LCS: knowing which specific characters matched doesn't affect future decisions (as long as we know the length so far)
In knapsack: exactly which items we took doesn't matter, only remaining capacity

Step 3: Minimize Redundancy

Check: Can I derive any state variable from others? If so, eliminate it.

Grid paths: we could track both (row, col) and total moves, but total moves = row + col, so it's redundant.

State Derivation Checklist

•List what changes between recursive calls
•Filter to what matters for the answer
•Eliminate redundancy (derived variables)
•Verify sufficiency — can you write the recurrence with this state?
•Calculate complexity — O(product of all dimension sizes)

Worked Example: Interleaving Strings

Problem: Given strings s1, s2, s3, determine if s3 can be formed by interleaving s1 and s2.

What changes?
- Position in s1 we've used (i)
- Position in s2 we've used (j)
- Position in s3 we're matching (k)
What matters?
- All three affect whether remaining characters can match
Eliminate redundancy?
- k = i + j (if we've used i chars from s1 and j from s2, we've matched i+j chars of s3)
Final state: (i, j) → 2D DP with O(m×n) states

Recurrence:

dp[i][j] = True if s3[0..i+j-1] can be formed by interleaving s1[0..i-1] and s2[0..j-1]
dp[i][j] = (dp[i-1][j] and s1[i-1] == s3[i+j-1]) or (dp[i][j-1] and s2[j-1] == s3[i+j-1])

interleaving_strings.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
def is_interleave(s1: str, s2: str, s3: str) -> bool:
    """
    Check if s3 is an interleaving of s1 and s2.
    
    State derivation:
    - i = chars used from s1
    - j = chars used from s2
    - k = i + j (redundant, eliminated)
    
    State: dp[i][j] = True if s1[0..i-1] and s2[0..j-1] can interleave to form s3[0..i+j-1]
    """
    m, n = len(s1), len(s2)
    
    # Quick check: lengths must match
    if m + n != len(s3):
        return False
    
    # dp[i][j] = True if s1[0..i-1] and s2[0..j-1] form s3[0..i+j-1]
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    
    # Base case: empty strings
    dp[0][0] = True
    
    # Base case: only using s1
    for i in range(1, m + 1):
        dp[i][0] = dp[i-1][0] and (s1[i-1] == s3[i-1])
    
    # Base case: only using s2
    for j in range(1, n + 1):
        dp[0][j] = dp[0][j-1] and (s2[j-1] == s3[j-1])
    
    # Fill the table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            # Current position in s3
            k = i + j - 1
            
            # Either extend from s1 or from s2
            from_s1 = dp[i-1][j] and (s1[i-1] == s3[k])
            from_s2 = dp[i][j-1] and (s2[j-1] == s3[k])
            
            dp[i][j] = from_s1 or from_s2
    
    return dp[m][n]
 
 
# Test
s1 = "aabcc"
s2 = "dbbca"
s3 = "aadbbcbcac"
print(f"Is interleaving: {is_interleave(s1, s2, s3)}")  # True

State Transitions in 2D DP

Once state is defined, we need transition rules: how does the answer for state (i, j) depend on other states?

Common Transition Patterns:

1. Adjacent Cells (Grid-style)

dp[i][j] depends on dp[i-1][j] and dp[i][j-1]

Used in: Grid paths, minimum path sum, LCS

2. Diagonal and Adjacent (Sequence comparison)

dp[i][j] depends on dp[i-1][j-1], dp[i-1][j], and dp[i][j-1]

Used in: Edit distance (add diagonal for substitution/match)

3. Expanding Ranges (Interval DP)

dp[i][j] depends on dp[i][k] and dp[k+1][j] for all k in [i, j-1]

Used in: Matrix chain multiplication, burst balloons

4. Shrinking Ranges (String DP)

dp[i][j] depends on dp[i+1][j-1]

Used in: Palindrome problems (shrink from both ends)

Converting Mermaid diagram...

Transition Determines Fill Order:

The way states depend on each other dictates how we fill the DP table:

Transition Type	Fill Order
Left and Up	Row by row, left to right
Diagonal and adjacent	Row by row, left to right
Range [i, j]	By increasing length (j-i)
Shrinking [i, j]	By decreasing length OR from edges inward

Why Fill Order Matters:

When we compute dp[i][j], all states it depends on must already be computed. Violating this order means accessing uninitialized values—a subtle bug that produces wrong answers.

transition_patterns.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
# ============================================================
# Range-style transitions: Matrix Chain Multiplication
# ============================================================
def matrix_chain_order(dims: list[int]) -> int:
    """
    Minimum scalar multiplications to multiply n matrices.
    
    State: dp[i][j] = min cost to multiply matrices i through j
    Transition: dp[i][j] = min over k of (dp[i][k] + dp[k+1][j] + cost(i,k,j))
    
    Fill order: By increasing chain length
    """
    n = len(dims) - 1  # Number of matrices
    
    # dp[i][j] = min cost to multiply matrices i to j (1-indexed)
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    
    # Base case: single matrix costs 0
    # dp[i][i] = 0 (already initialized)
    
    # Fill by increasing chain length
    for length in range(2, n + 1):  # length = j - i + 1
        for i in range(1, n - length + 2):
            j = i + length - 1
            dp[i][j] = float('inf')
            
            # Try all split points
            for k in range(i, j):
                # Cost = multiply (i to k) + (k+1 to j) + combine
                cost = dp[i][k] + dp[k+1][j] + dims[i-1] * dims[k] * dims[j]
                dp[i][j] = min(dp[i][j], cost)
    
    return dp[1][n]
 
 
# ============================================================
# Shrinking range: Longest Palindromic Substring (DP version)
# ============================================================
def longest_palindrome_substring(s: str) -> str:
    """
    State: dp[i][j] = True if s[i:j+1] is palindrome
    Transition: dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]
    
    Fill order: By increasing length (so dp[i+1][j-1] is ready)
    """
    n = len(s)
    if n == 0:
        return ""
    
    dp = [[False] * n for _ in range(n)]
    
    # Track best palindrome found
    start, max_len = 0, 1
    
    # Base case: single characters
    for i in range(n):
        dp[i][i] = True
    
    # Base case: pairs
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            dp[i][i + 1] = True
            start, max_len = i, 2
    
    # Fill for lengths 3+
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            
            # s[i:j+1] is palindrome if ends match and middle is palindrome
            if s[i] == s[j] and dp[i + 1][j - 1]:
                dp[i][j] = True
                start, max_len = i, length
    
    return s[start:start + max_len]
 
 
# Examples
print(f"Matrix chain: {matrix_chain_order([10, 30, 5, 60])}")
print(f"Longest palindrome: '{longest_palindrome_substring('babad')}'")

Visualizing 2D State Space

Developing geometric intuition for 2D DP tables accelerates understanding and debugging. Each 2D state space has a characteristic shape:

Full Rectangle (Position-Position)

LCS, edit distance, grid paths: Every (i, j) combination is valid.

+---+---+---+---+
| 0 | 1 | 1 | 1 |
+---+---+---+---+
| 1 | 1 | 2 | 2 |
+---+---+---+---+
| 1 | 2 | 2 | 3 |
+---+---+---+---+

Answer at corner.

Upper Triangle (Range i ≤ j)

Matrix chain, palindrome: Only ranges where start ≤ end are meaningful.

+---+---+---+---+
| * | * | * | * |
+---+---+---+---+
|   | * | * | * |
+---+---+---+---+
|   |   | * | * |
+---+---+---+---+
|   |   |   | * |
+---+---+---+---+

Diagonal = base cases (single elements).

Staircase (Knapsack-style)

Capacity constraints may limit valid states.

+---+---+---+---+---+
| * | * | * | * | * |  cap=0 to max
+---+---+---+---+---+
| * | * | * | * | * |
+---+---+---+---+---+
| * | * | * | * | * |
+---+---+---+---+---+
item 0 to n

Full rectangle, answer at corner.

Debugging with Visualization:

When your DP solution fails:

Print the table for a small example
Check base cases — Are edge cells correct?
Trace manually — Do interior cells follow the recurrence?
Look for patterns — Unexpected zeros? Wrong growth direction?

Visualization also helps understand space optimization: if you only need adjacent rows, you can see this visually.

Draw Before You Code

For any 2D DP problem, draw a small table (4×4 or 5×5) and fill it by hand before writing code. This catches recurrence errors, clarifies base cases, and builds intuition. Many interview candidates skip this step and spend more time debugging.

Common Pitfalls in 2D State Design

Even experienced practitioners make these mistakes. Learn from them:

Pitfall 1: Insufficient State

Forgetting a necessary dimension. Example: Attempting house robber with circular arrangement using only dp[i], forgetting we need to track whether we took the first house.

Fix: Ask "Does knowing only (these variables) uniquely identify my subproblem?"

Pitfall 2: Excessive State

Including unnecessary information. Example: In LCS, tracking the actual LCS string built so far instead of just its length.

Fix: Ask "If I removed this variable, could I still write the recurrence?"

Pitfall 3: Wrong State Semantics

Misunderstanding what the state represents. Example: Confusing "dp[i][j] = LCS of X[0..i-1] and Y[0..j-1]" with "dp[i][j] = LCS of X[i..] and Y[j..]".

Fix: Write a precise English definition before coding.

Pitfall 4: Incorrect Base Cases

Base case errors cause entire tables to be wrong. Example: Forgetting dp[0][j] = j in edit distance (need j insertions to build Y from empty X).

Fix: Derive base cases from state semantics, not by pattern matching.

Common Errors

•Off-by-one: dp table size m+1 but accessing dp[m]
•Wrong initialization: default 0 when should be infinity
•Reversed indices: dp[j][i] instead of dp[i][j]
•Missing edge cases: single character strings, empty inputs

Best Practices

•Write state semantics as a comment
•Derive base cases from definition
•Test with trivial inputs first
•Print table for small manual verification

The Semantics Test

Before coding, answer: 'What exactly does dp[3][5] mean in my problem?' If you can't give a precise answer, stop and clarify. Vague state understanding leads to vague (wrong) code.

Beyond 2D: When More Indices Are Needed

Some problems require 3D, 4D, or even higher-dimensional state. The principles remain the same, but complexity grows.

When 3D State Arises:

Three sequences: LCS of three strings → dp[i][j][k]
Two agents: Cherry pickup with two people → dp[r1][c1][c2] (r2 derived)
Extra constraint: Knapsack with two constraints (weight and volume) → dp[i][w][v]

Example: Cherry Pickup II

Two robots start at top row corners, move down, collect cherries. State: dp[row][col1][col2] = max cherries when robot 1 at col1 and robot 2 at col2 in given row.

3D because: row (shared), col1 (robot 1), col2 (robot 2)
O(n × m²) states for m columns, n rows

higher_dimensional_dp.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
def cherry_pickup_ii(grid: list[list[int]]) -> int:
    """
    Two robots start at top corners, move down collecting cherries.
    
    State: dp[row][c1][c2] = max cherries when robot 1 at col c1,
           robot 2 at col c2, both in given row
    
    3D DP because we track:
    - Current row (shared, can be space-optimized away)
    - Robot 1's column
    - Robot 2's column
    """
    rows, cols = len(grid), len(grid[0])
    
    # dp[c1][c2] = max cherries for current row
    # (we'll use 2D + rolling to save space)
    dp = [[float('-inf')] * cols for _ in range(cols)]
    
    # Base case: row 0, robot 1 at col 0, robot 2 at col (cols-1)
    dp[0][cols - 1] = grid[0][0] + grid[0][cols - 1]
    
    for row in range(1, rows):
        new_dp = [[float('-inf')] * cols for _ in range(cols)]
        
        for c1 in range(cols):
            for c2 in range(cols):
                # Try all moves from previous row
                for dc1 in [-1, 0, 1]:  # Robot 1 can move left, stay, right
                    for dc2 in [-1, 0, 1]:  # Robot 2 can move left, stay, right
                        pc1 = c1 - dc1
                        pc2 = c2 - dc2
                        
                        if 0 <= pc1 < cols and 0 <= pc2 < cols:
                            # Cherries collected
                            cherries = grid[row][c1]
                            if c1 != c2:  # Don't double-count same cell
                                cherries += grid[row][c2]
                            
                            new_dp[c1][c2] = max(
                                new_dp[c1][c2],
                                dp[pc1][pc2] + cherries
                            )
        
        dp = new_dp
    
    return max(max(row) for row in dp)
 
 
# Example
grid = [
    [3, 1, 1],
    [2, 5, 1],
    [1, 5, 5],
    [2, 1, 1]
]
print(f"Max cherries: {cherry_pickup_ii(grid)}")  # Output: 24

Managing Complexity:

As dimensions increase, complexity explodes. Strategies to manage:

Space optimization: Roll through one dimension (as shown above)
Bitmask compression: Represent subset as integer (for small sets)
Pruning: Skip provably suboptimal states
Problem reduction: Sometimes 3D can be reformulated as 2D

Practical Limits:

Dimensions	Typical Size	States	Feasibility
2D	1000×1000	10^6	Easy
3D	100×100×100	10^6	Feasible
4D	50×50×50×50	6×10^6	Borderline
Bitmask	20 items	2^20 ≈ 10^6	Feasible

When in Doubt, Start 2D

Most DP problems in interviews and contests are solvable with 2D state. If you find yourself reaching for 3D+, double-check: Is there redundancy? Can a dimension be eliminated? Often, apparent 3D problems have 2D solutions with clever state design.

Summary and Key Takeaways

State design is the heart of dynamic programming. A well-chosen state makes the problem tractable; a poor choice leads to either impossibility or unnecessary complexity. Let's consolidate our understanding:

Key Concepts Mastered

•State is subproblem identity — It captures exactly what's needed to describe and solve a subproblem.
•2D state arises from: two sequences, grid structure, range processing, or index-constraint pairs.
•Common patterns: position-position, grid coordinates, [start, end] ranges, index-capacity.
•Derivation framework: List what changes → filter to what matters → eliminate redundancy → verify sufficiency.
•Transitions determine fill order — Ensure dependencies are computed before dependents.
•Visualization aids debugging — Draw small tables, trace manually, catch errors early.

The Master Skill:

The ability to look at a problem and say "This needs dp[i][j] where i represents X and j represents Y" is what separates DP experts from those who struggle. This skill comes from:

Practice on many 2D DP problems
Always writing explicit state semantics
Analyzing why the state works (or doesn't)

What's Next:

With state design mastered, we'll explore how to interpret and use the DP table geometrically. Understanding table structure enables faster debugging, clearer thinking, and elegant space optimizations.

Page Complete

You now understand the art of 2D state design—when to use two indices, what they should represent, and how to derive them systematically. This is the core skill for solving novel DP problems. Next, we'll explore how to interpret and leverage the DP table structure for even deeper understanding.

3 / 4

Loading learning content...

Data Structures & Algorithms2D DP Problems — Grid Paths & LCS

2D Dynamic Programming — Grid Paths & Longest Common Subsequence

LevelIntermediate

Duration75 mins

Topic2D DP Problems — Grid Paths & LCS

3 / 4

State: Two Indices

The Art of State Design in 2D DP

What You Will Learn

What Is State in Dynamic Programming?

Definition:

In dynamic programming, state is the minimal information needed to describe a subproblem uniquely. The state determines:

What subproblem we're solving
What the answer to that subproblem is
How larger subproblems depend on smaller ones

The State Space:

The collection of all possible states forms the state space. The size of this space determines the time and space complexity of our DP solution:

1D DP: State is a single variable → O(n) states
2D DP: State is a pair of variables → O(n×m) states
3D DP: Three variables → O(n×m×k) states

The DP table is just a concrete representation of the state space, where each cell stores the answer for one state.

State Examples Across Problem Types
Problem	State	Meaning	Table Size
Fibonacci	n	n-th Fibonacci number	O(n)
Climbing Stairs	step	Ways to reach step i	O(n)
Grid Paths	(row, col)	Ways to reach cell (row, col)	O(m×n)
LCS	(i, j)	LCS of X[0..i-1] and Y[0..j-1]	O(m×n)
0/1 Knapsack	(item, capacity)	Max value with items 0..i and capacity c	O(n×W)
Matrix Chain	(i, j)	Min cost to multiply matrices i..j	O(n²)

State = Subproblem Identifier

When Do We Need Two Indices?

Not every problem needs 2D state. Here are the key indicators that suggest two indices are necessary:

Signal 1: Two Independent Sequences or Dimensions

When the problem involves two separate sequences (strings, arrays) that we're comparing, aligning, or processing together, we typically need an index for each.

Examples:

LCS: comparing two strings → indices (i, j) for positions in each
Edit Distance: transforming one string to another → same structure
Interleaving Strings: combining two strings → track position in each

Signal 2: Grid or Matrix Structure

Problems defined on 2D grids naturally need row and column indices.

Examples:

Grid paths, minimum path sum, dungeon game
Matrix chain multiplication (though indexed by subrange)

Signal 3: Range or Interval Processing

When we need to consider contiguous ranges of a single sequence, we use two indices for the start and end of the range.

Examples:

Matrix chain multiplication: dp[i][j] = min cost for matrices i to j
Palindrome partitioning: dp[i][j] = whether s[i..j] is palindrome
Burst balloons: dp[i][j] = max coins from bursting i to j

Converting Mermaid diagram...

The Key Test:

Ask yourself: Can I describe a subproblem completely with a single number?

Fibonacci: Yes, just need n. → 1D DP
LCS: No, need position in each string. → 2D DP
Grid paths: No, need row and column. → 2D DP
House robber: Yes, just need index up to which we've decided. → 1D DP
Knapsack: No, need item index AND remaining capacity. → 2D DP

If one number isn't enough to uniquely identify subproblems, you need more dimensions.

Minimality Matters

Common 2D State Patterns

Through experience, certain 2D state patterns recur. Recognizing these accelerates problem-solving:

Pattern 1: Position-Position (Two Sequences)

State: dp[i][j] = result for X[0..i-1] combined with Y[0..j-1]

Used in: LCS, edit distance, interleaving strings, regular expression matching.

Pattern 2: Position-Position (Grid)

State: dp[row][col] = result for reaching/leaving cell (row, col)

Used in: Unique paths, minimum path sum, dungeon game, cherry pickup.

Pattern 3: Range (Start-End)

State: dp[i][j] = result for subarray/substring from index i to j

Used in: Matrix chain multiplication, burst balloons, palindrome-related problems.

Pattern 4: Index-Capacity (Knapsack-style)

State: dp[i][c] = result considering items 0..i-1 with capacity/budget c

Used in: 0/1 knapsack, coin change (2D variant), subset sum with targets.

state_patterns_examples.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
# ============================================================
# Pattern 1: Position-Position (Two Sequences)
# ============================================================
def edit_distance(X: str, Y: str) -> int:
    """
    State: dp[i][j] = min edits to transform X[0..i-1] to Y[0..j-1]
    
    Two sequences → two indices (i for X, j for Y)
    """
    m, n = len(X), len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Base cases: transforming to/from empty string
    for i in range(m + 1):
        dp[i][0] = i  # Delete all characters from X
    for j in range(n + 1):
        dp[0][j] = j  # Insert all characters of Y
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i-1] == Y[j-1]:
                dp[i][j] = dp[i-1][j-1]  # No operation needed
            else:
                dp[i][j] = 1 + min(
                    dp[i-1][j],    # Delete from X
                    dp[i][j-1],    # Insert into X
                    dp[i-1][j-1]   # Replace in X
                )
    
    return dp[m][n]
 
 
# ============================================================
# Pattern 2: Position-Position (Grid)
# ============================================================
def min_path_sum(grid: list[list[int]]) -> int:
    """
    State: dp[row][col] = min sum to reach (row, col) from (0, 0)
    
    Grid → two indices (row, column)
    """
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]
    
    # Base case: starting cell
    dp[0][0] = grid[0][0]
    
    # First row: can only come from left
    for j in range(1, n):
        dp[0][j] = dp[0][j-1] + grid[0][j]
    
    # First column: can only come from above
    for i in range(1, m):
        dp[i][0] = dp[i-1][0] + grid[i][0]
    
    # Fill rest
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
    
    return dp[m-1][n-1]
 
 
# ============================================================
# Pattern 3: Range (Start-End)
# ============================================================
def is_palindrome_range(s: str) -> list[list[bool]]:
    """
    State: dp[i][j] = True if s[i..j] is a palindrome
    
    Range → two indices (start, end of substring)
    """
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    
    # Base case: single characters are palindromes
    for i in range(n):
        dp[i][i] = True
    
    # Base case: two characters
    for i in range(n - 1):
        dp[i][i+1] = (s[i] == s[i+1])
    
    # Fill for lengths 3 and up
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            # s[i..j] is palindrome if ends match and middle is palindrome
            dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]
    
    return dp
 
 
# ============================================================
# Pattern 4: Index-Capacity (Knapsack-style)
# ============================================================
def knapsack_01(weights: list[int], values: list[int], capacity: int) -> int:
    """
    State: dp[i][c] = max value using items 0..i-1 with capacity c
    
    Items + constraint → two indices (item index, remaining capacity)
    """
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for c in range(capacity + 1):
            # Don't take item i-1
            dp[i][c] = dp[i-1][c]
            
            # Take item i-1 if it fits
            if weights[i-1] <= c:
                dp[i][c] = max(
                    dp[i][c],
                    values[i-1] + dp[i-1][c - weights[i-1]]
                )
    
    return dp[n][capacity]
 
 
# Examples
print(f"Edit distance 'kitten' → 'sitting': {edit_distance('kitten', 'sitting')}")
print(f"Min path sum: {min_path_sum([[1,3,1],[1,5,1],[4,2,1]])}")
print(f"Knapsack: {knapsack_01([2,3,4,5], [3,4,5,6], 5)}")

Pattern Recognition = Speed

Deriving State from Problem Structure

When patterns don't immediately apply, we need a systematic approach to derive state. Here's a framework:

Step 1: Identify What Changes

Ask: As I solve this problem recursively, what information changes between recursive calls?

In grid paths: my current position (row, col) changes
In LCS: how much of each string I've processed (i, j) changes
In knapsack: which items I've considered (i) and remaining capacity (c) change

Each changing piece of information is a candidate for a state dimension.

Step 2: Determine What Affects the Answer

Not everything that changes matters. Ask: Does knowing X affect my optimal decision or answer?

In LCS: knowing which specific characters matched doesn't affect future decisions (as long as we know the length so far)
In knapsack: exactly which items we took doesn't matter, only remaining capacity

Step 3: Minimize Redundancy

Check: Can I derive any state variable from others? If so, eliminate it.

Grid paths: we could track both (row, col) and total moves, but total moves = row + col, so it's redundant.

State Derivation Checklist

•List what changes between recursive calls
•Filter to what matters for the answer
•Eliminate redundancy (derived variables)
•Verify sufficiency — can you write the recurrence with this state?
•Calculate complexity — O(product of all dimension sizes)

Worked Example: Interleaving Strings

Problem: Given strings s1, s2, s3, determine if s3 can be formed by interleaving s1 and s2.

What changes?
- Position in s1 we've used (i)
- Position in s2 we've used (j)
- Position in s3 we're matching (k)
What matters?
- All three affect whether remaining characters can match
Eliminate redundancy?
- k = i + j (if we've used i chars from s1 and j from s2, we've matched i+j chars of s3)
Final state: (i, j) → 2D DP with O(m×n) states

Recurrence:

dp[i][j] = True if s3[0..i+j-1] can be formed by interleaving s1[0..i-1] and s2[0..j-1]
dp[i][j] = (dp[i-1][j] and s1[i-1] == s3[i+j-1]) or (dp[i][j-1] and s2[j-1] == s3[i+j-1])

interleaving_strings.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
def is_interleave(s1: str, s2: str, s3: str) -> bool:
    """
    Check if s3 is an interleaving of s1 and s2.
    
    State derivation:
    - i = chars used from s1
    - j = chars used from s2
    - k = i + j (redundant, eliminated)
    
    State: dp[i][j] = True if s1[0..i-1] and s2[0..j-1] can interleave to form s3[0..i+j-1]
    """
    m, n = len(s1), len(s2)
    
    # Quick check: lengths must match
    if m + n != len(s3):
        return False
    
    # dp[i][j] = True if s1[0..i-1] and s2[0..j-1] form s3[0..i+j-1]
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    
    # Base case: empty strings
    dp[0][0] = True
    
    # Base case: only using s1
    for i in range(1, m + 1):
        dp[i][0] = dp[i-1][0] and (s1[i-1] == s3[i-1])
    
    # Base case: only using s2
    for j in range(1, n + 1):
        dp[0][j] = dp[0][j-1] and (s2[j-1] == s3[j-1])
    
    # Fill the table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            # Current position in s3
            k = i + j - 1
            
            # Either extend from s1 or from s2
            from_s1 = dp[i-1][j] and (s1[i-1] == s3[k])
            from_s2 = dp[i][j-1] and (s2[j-1] == s3[k])
            
            dp[i][j] = from_s1 or from_s2
    
    return dp[m][n]
 
 
# Test
s1 = "aabcc"
s2 = "dbbca"
s3 = "aadbbcbcac"
print(f"Is interleaving: {is_interleave(s1, s2, s3)}")  # True

State Transitions in 2D DP

Once state is defined, we need transition rules: how does the answer for state (i, j) depend on other states?

Common Transition Patterns:

1. Adjacent Cells (Grid-style)

dp[i][j] depends on dp[i-1][j] and dp[i][j-1]

Used in: Grid paths, minimum path sum, LCS

2. Diagonal and Adjacent (Sequence comparison)

dp[i][j] depends on dp[i-1][j-1], dp[i-1][j], and dp[i][j-1]

Used in: Edit distance (add diagonal for substitution/match)

3. Expanding Ranges (Interval DP)

dp[i][j] depends on dp[i][k] and dp[k+1][j] for all k in [i, j-1]

Used in: Matrix chain multiplication, burst balloons

4. Shrinking Ranges (String DP)

dp[i][j] depends on dp[i+1][j-1]

Used in: Palindrome problems (shrink from both ends)

Converting Mermaid diagram...

Transition Determines Fill Order:

The way states depend on each other dictates how we fill the DP table:

Transition Type	Fill Order
Left and Up	Row by row, left to right
Diagonal and adjacent	Row by row, left to right
Range [i, j]	By increasing length (j-i)
Shrinking [i, j]	By decreasing length OR from edges inward

Why Fill Order Matters:

When we compute dp[i][j], all states it depends on must already be computed. Violating this order means accessing uninitialized values—a subtle bug that produces wrong answers.

transition_patterns.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
# ============================================================
# Range-style transitions: Matrix Chain Multiplication
# ============================================================
def matrix_chain_order(dims: list[int]) -> int:
    """
    Minimum scalar multiplications to multiply n matrices.
    
    State: dp[i][j] = min cost to multiply matrices i through j
    Transition: dp[i][j] = min over k of (dp[i][k] + dp[k+1][j] + cost(i,k,j))
    
    Fill order: By increasing chain length
    """
    n = len(dims) - 1  # Number of matrices
    
    # dp[i][j] = min cost to multiply matrices i to j (1-indexed)
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    
    # Base case: single matrix costs 0
    # dp[i][i] = 0 (already initialized)
    
    # Fill by increasing chain length
    for length in range(2, n + 1):  # length = j - i + 1
        for i in range(1, n - length + 2):
            j = i + length - 1
            dp[i][j] = float('inf')
            
            # Try all split points
            for k in range(i, j):
                # Cost = multiply (i to k) + (k+1 to j) + combine
                cost = dp[i][k] + dp[k+1][j] + dims[i-1] * dims[k] * dims[j]
                dp[i][j] = min(dp[i][j], cost)
    
    return dp[1][n]
 
 
# ============================================================
# Shrinking range: Longest Palindromic Substring (DP version)
# ============================================================
def longest_palindrome_substring(s: str) -> str:
    """
    State: dp[i][j] = True if s[i:j+1] is palindrome
    Transition: dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]
    
    Fill order: By increasing length (so dp[i+1][j-1] is ready)
    """
    n = len(s)
    if n == 0:
        return ""
    
    dp = [[False] * n for _ in range(n)]
    
    # Track best palindrome found
    start, max_len = 0, 1
    
    # Base case: single characters
    for i in range(n):
        dp[i][i] = True
    
    # Base case: pairs
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            dp[i][i + 1] = True
            start, max_len = i, 2
    
    # Fill for lengths 3+
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            
            # s[i:j+1] is palindrome if ends match and middle is palindrome
            if s[i] == s[j] and dp[i + 1][j - 1]:
                dp[i][j] = True
                start, max_len = i, length
    
    return s[start:start + max_len]
 
 
# Examples
print(f"Matrix chain: {matrix_chain_order([10, 30, 5, 60])}")
print(f"Longest palindrome: '{longest_palindrome_substring('babad')}'")

Visualizing 2D State Space

Developing geometric intuition for 2D DP tables accelerates understanding and debugging. Each 2D state space has a characteristic shape:

Full Rectangle (Position-Position)

LCS, edit distance, grid paths: Every (i, j) combination is valid.

+---+---+---+---+
| 0 | 1 | 1 | 1 |
+---+---+---+---+
| 1 | 1 | 2 | 2 |
+---+---+---+---+
| 1 | 2 | 2 | 3 |
+---+---+---+---+

Answer at corner.

Upper Triangle (Range i ≤ j)

Matrix chain, palindrome: Only ranges where start ≤ end are meaningful.

+---+---+---+---+
| * | * | * | * |
+---+---+---+---+
|   | * | * | * |
+---+---+---+---+
|   |   | * | * |
+---+---+---+---+
|   |   |   | * |
+---+---+---+---+

Diagonal = base cases (single elements).

Staircase (Knapsack-style)

Capacity constraints may limit valid states.

+---+---+---+---+---+
| * | * | * | * | * |  cap=0 to max
+---+---+---+---+---+
| * | * | * | * | * |
+---+---+---+---+---+
| * | * | * | * | * |
+---+---+---+---+---+
item 0 to n

Full rectangle, answer at corner.

Debugging with Visualization:

When your DP solution fails:

Print the table for a small example
Check base cases — Are edge cells correct?
Trace manually — Do interior cells follow the recurrence?
Look for patterns — Unexpected zeros? Wrong growth direction?

Visualization also helps understand space optimization: if you only need adjacent rows, you can see this visually.

Draw Before You Code

Common Pitfalls in 2D State Design

Even experienced practitioners make these mistakes. Learn from them:

Pitfall 1: Insufficient State

Forgetting a necessary dimension. Example: Attempting house robber with circular arrangement using only dp[i], forgetting we need to track whether we took the first house.

Fix: Ask "Does knowing only (these variables) uniquely identify my subproblem?"

Pitfall 2: Excessive State

Including unnecessary information. Example: In LCS, tracking the actual LCS string built so far instead of just its length.

Fix: Ask "If I removed this variable, could I still write the recurrence?"

Pitfall 3: Wrong State Semantics

Misunderstanding what the state represents. Example: Confusing "dp[i][j] = LCS of X[0..i-1] and Y[0..j-1]" with "dp[i][j] = LCS of X[i..] and Y[j..]".

Fix: Write a precise English definition before coding.

Pitfall 4: Incorrect Base Cases

Base case errors cause entire tables to be wrong. Example: Forgetting dp[0][j] = j in edit distance (need j insertions to build Y from empty X).

Fix: Derive base cases from state semantics, not by pattern matching.

Common Errors

•Off-by-one: dp table size m+1 but accessing dp[m]
•Wrong initialization: default 0 when should be infinity
•Reversed indices: dp[j][i] instead of dp[i][j]
•Missing edge cases: single character strings, empty inputs

Best Practices

•Write state semantics as a comment
•Derive base cases from definition
•Test with trivial inputs first
•Print table for small manual verification

The Semantics Test

Before coding, answer: 'What exactly does dp[3][5] mean in my problem?' If you can't give a precise answer, stop and clarify. Vague state understanding leads to vague (wrong) code.

Beyond 2D: When More Indices Are Needed

Some problems require 3D, 4D, or even higher-dimensional state. The principles remain the same, but complexity grows.

When 3D State Arises:

Three sequences: LCS of three strings → dp[i][j][k]
Two agents: Cherry pickup with two people → dp[r1][c1][c2] (r2 derived)
Extra constraint: Knapsack with two constraints (weight and volume) → dp[i][w][v]

Example: Cherry Pickup II

Two robots start at top row corners, move down, collect cherries. State: dp[row][col1][col2] = max cherries when robot 1 at col1 and robot 2 at col2 in given row.

3D because: row (shared), col1 (robot 1), col2 (robot 2)
O(n × m²) states for m columns, n rows

higher_dimensional_dp.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
def cherry_pickup_ii(grid: list[list[int]]) -> int:
    """
    Two robots start at top corners, move down collecting cherries.
    
    State: dp[row][c1][c2] = max cherries when robot 1 at col c1,
           robot 2 at col c2, both in given row
    
    3D DP because we track:
    - Current row (shared, can be space-optimized away)
    - Robot 1's column
    - Robot 2's column
    """
    rows, cols = len(grid), len(grid[0])
    
    # dp[c1][c2] = max cherries for current row
    # (we'll use 2D + rolling to save space)
    dp = [[float('-inf')] * cols for _ in range(cols)]
    
    # Base case: row 0, robot 1 at col 0, robot 2 at col (cols-1)
    dp[0][cols - 1] = grid[0][0] + grid[0][cols - 1]
    
    for row in range(1, rows):
        new_dp = [[float('-inf')] * cols for _ in range(cols)]
        
        for c1 in range(cols):
            for c2 in range(cols):
                # Try all moves from previous row
                for dc1 in [-1, 0, 1]:  # Robot 1 can move left, stay, right
                    for dc2 in [-1, 0, 1]:  # Robot 2 can move left, stay, right
                        pc1 = c1 - dc1
                        pc2 = c2 - dc2
                        
                        if 0 <= pc1 < cols and 0 <= pc2 < cols:
                            # Cherries collected
                            cherries = grid[row][c1]
                            if c1 != c2:  # Don't double-count same cell
                                cherries += grid[row][c2]
                            
                            new_dp[c1][c2] = max(
                                new_dp[c1][c2],
                                dp[pc1][pc2] + cherries
                            )
        
        dp = new_dp
    
    return max(max(row) for row in dp)
 
 
# Example
grid = [
    [3, 1, 1],
    [2, 5, 1],
    [1, 5, 5],
    [2, 1, 1]
]
print(f"Max cherries: {cherry_pickup_ii(grid)}")  # Output: 24

Managing Complexity:

As dimensions increase, complexity explodes. Strategies to manage:

Space optimization: Roll through one dimension (as shown above)
Bitmask compression: Represent subset as integer (for small sets)
Pruning: Skip provably suboptimal states
Problem reduction: Sometimes 3D can be reformulated as 2D

Practical Limits:

Dimensions	Typical Size	States	Feasibility
2D	1000×1000	10^6	Easy
3D	100×100×100	10^6	Feasible
4D	50×50×50×50	6×10^6	Borderline
Bitmask	20 items	2^20 ≈ 10^6	Feasible

When in Doubt, Start 2D

Summary and Key Takeaways

Key Concepts Mastered

•State is subproblem identity — It captures exactly what's needed to describe and solve a subproblem.
•2D state arises from: two sequences, grid structure, range processing, or index-constraint pairs.
•Common patterns: position-position, grid coordinates, [start, end] ranges, index-capacity.
•Derivation framework: List what changes → filter to what matters → eliminate redundancy → verify sufficiency.
•Transitions determine fill order — Ensure dependencies are computed before dependents.
•Visualization aids debugging — Draw small tables, trace manually, catch errors early.

The Master Skill:

The ability to look at a problem and say "This needs dp[i][j] where i represents X and j represents Y" is what separates DP experts from those who struggle. This skill comes from:

Practice on many 2D DP problems
Always writing explicit state semantics
Analyzing why the state works (or doesn't)

What's Next:

Page Complete

3 / 4