13.6 Two-Dimensional Dynamic Programming

One-dimensional dynamic programming models progress along a single axis. Many problems, however, involve two independent dimensions. A string can be compared against another string. A path can move across rows and columns of a grid. A resource allocation problem may track both items processed and capacity remaining.

In such situations, a single state variable is insufficient. The solution requires a state that captures progress in two directions simultaneously. This leads naturally to two-dimensional dynamic programming.

The techniques introduced in this section appear throughout algorithm design. Longest common subsequence, edit distance, knapsack, sequence alignment, matrix path problems, and many graph algorithms rely on two-dimensional state spaces. Understanding how to design, visualize, and optimize these state spaces is a critical step toward more advanced dynamic programming methods.

Problem

How do we design and implement dynamic programming solutions whose states depend on two variables?

Understanding Two-Dimensional States

A typical two-dimensional state has the form:

$$ dp[i][j] $$

The variables may represent:

row and column
two sequence positions
item count and capacity
start and end positions
time and resource level

Unlike one-dimensional dynamic programming, where states form a line, two-dimensional states form a grid.

For example:

dp[i][j]

might represent:

best solution using
first i elements of A
and first j elements of B

Each coordinate identifies a unique subproblem.

Example: Grid Path Counting

Consider an (m \times n) grid.

You begin at the upper-left corner and may move only:

right
down

How many paths lead to cell ((i,j))?

State:

$$ dp[i][j] $$

Meaning:

number of paths
to reach cell (i,j)

To arrive at ((i,j)), the previous step must come from:

above
left

Therefore:

$$ dp[i][j] = dp[i-1][j] + dp[i][j-1] $$

Base conditions:

$$ dp[0][j]=1 $$

$$ dp[i][0]=1 $$

Implementation:

for i := 1; i < rows; i++ {
    for j := 1; j < cols; j++ {
        dp[i][j] =
            dp[i-1][j] +
            dp[i][j-1]
    }
}

This example demonstrates the most fundamental two-dimensional dependency pattern.

Visualizing the State Space

A two-dimensional DP table can be viewed as a coordinate system.

(0,0) (0,1) (0,2)

(1,0) (1,1) (1,2)

(2,0) (2,1) (2,2)

Each cell represents a subproblem.

The recurrence determines dependency directions.

For grid paths:

      ↑

left → current

Because dependencies point upward and leftward, a row-major traversal naturally satisfies all requirements.

Example: Minimum Path Sum

Suppose each grid cell contains a cost.

Goal:

minimum cost
from start to finish

State:

$$ dp[i][j] $$

Meaning:

minimum cost
to reach cell (i,j)

Recurrence:

$$ dp[i][j] = grid[i][j] + \min ( dp[i-1][j], dp[i][j-1] ) $$

The structure is identical to path counting.

Only the aggregation operator changes:

counting uses addition
optimization uses minimum

This pattern appears repeatedly in dynamic programming.

Example: Longest Common Subsequence

Given strings:

A
B

State:

$$ dp[i][j] $$

Meaning:

length of the LCS
between prefixes

A[0...i)
B[0...j)

Suppose:

A[i-1] == B[j-1]

Then:

$$ dp[i][j] = 1+ dp[i-1][j-1] $$

Otherwise:

$$ dp[i][j] = \max ( dp[i-1][j], dp[i][j-1] ) $$

Notice the dependency pattern:

upper-left
up
left

This triangular dependency structure is common in sequence comparison problems.

Implementation:

for i := 1; i <= n; i++ {
    for j := 1; j <= m; j++ {

        if a[i-1] == b[j-1] {
            dp[i][j] =
                dp[i-1][j-1] + 1
        } else {
            dp[i][j] =
                max(
                    dp[i-1][j],
                    dp[i][j-1],
                )
        }
    }
}

Example: Edit Distance

The edit distance problem extends the LCS idea.

Allowed operations:

insert
delete
replace

State:

$$ dp[i][j] $$

Meaning:

minimum edits
to transform

A[0...i)

into

B[0...j)

If characters match:

$$ dp[i][j] = dp[i-1][j-1] $$

Otherwise:

$$ dp[i][j] = 1+ \min ( dp[i-1][j], dp[i][j-1], dp[i-1][j-1] ) $$

The recurrence directly models the three possible operations.

This illustrates an important principle:

A recurrence often mirrors the legal operations of the problem.

Example: 0/1 Knapsack

State:

$$ dp[i][w] $$

Meaning:

maximum value
using first i items
with capacity w

Two decisions exist:

Skip Item

$$ dp[i-1][w] $$

Take Item

$$ dp[i-1][w-weight_i] + value_i $$

Recurrence:

$$ dp[i][w] = \max ( dp[i-1][w], dp[i-1][w-weight_i]+value_i ) $$

Unlike grid problems, the second dimension represents a resource rather than a position.

The underlying dynamic programming principles remain unchanged.

Dependency Direction

Every two-dimensional recurrence defines movement through the table.

Common patterns include:

Left and Up

←
↑

Examples:

grid paths
edit distance
LCS

Previous Row

↑

Examples:

knapsack
scheduling

Diagonal

↖

Examples:

sequence matching
string alignment

Understanding these directions determines iteration order.

Initialization Strategies

Most bugs in two-dimensional dynamic programming occur near table boundaries.

For LCS:

$$ dp[0][j]=0 $$

$$ dp[i][0]=0 $$

For grid paths:

$$ dp[0][j]=1 $$

$$ dp[i][0]=1 $$

For edit distance:

$$ dp[0][j]=j $$

$$ dp[i][0]=i $$

The correct initialization follows directly from the meaning of the state.

A useful habit is to write the state definition first and derive boundary conditions afterward.

Memory Layout

A two-dimensional table:

dp := make([][]int, rows)

typically requires:

$$ O(rows \times cols) $$

memory.

For large state spaces, memory consumption may dominate running time.

Understanding dependencies often reveals opportunities for compression.

Row Compression

Consider:

$$ dp[i][j] = f( dp[i-1][j], dp[i][j-1] ) $$

Only the current row and previous row may be needed.

Instead of storing:

all rows

store:

previous row
current row

Memory decreases from:

$$ O(nm) $$

to:

$$ O(m) $$

This optimization is extremely common in production implementations.

Common Mistakes

Incorrect State Meaning

Example:

dp[i][j]

sometimes interpreted as:

first i elements

and elsewhere as:

up to index i

These meanings differ by one position and frequently produce off-by-one errors.

Wrong Iteration Order

Dependencies must be computed before use.

Always verify dependency directions before writing loops.

Boundary Access

Expressions such as:

dp[i-1][j]

become invalid when:

i = 0

Initialization should eliminate such cases.

Excessive State Dimensions

Many beginners introduce unnecessary variables.

Ask:

Can one dimension be derived from the others?

If yes, remove it.

Complexity Analysis

Suppose:

$$ n $$

possible values for the first dimension and:

$$ m $$

possible values for the second.

State count:

$$ O(nm) $$

If each state performs constant work:

$$ O(nm) $$

time.

Memory:

$$ O(nm) $$

before optimization.

These formulas appear repeatedly throughout dynamic programming literature.

Takeaway

Two-dimensional dynamic programming extends the ideas of one-dimensional state spaces to problems involving two independent variables. Each state represents a coordinate in a grid of subproblems, and recurrence relations describe how information flows through that grid. Many of the most important dynamic programming algorithms, including longest common subsequence, edit distance, knapsack, and grid optimization problems, rely on this model. Once state meanings, dependency directions, and boundary conditions are clearly defined, the resulting implementations often become straightforward and highly systematic.