Command Palette

Search for a command to run...

From 1D to 2D: When You Need Two Parameters

Yesterday we mastered 1D dynamic programming, where state could be captured by a single parameter: dp[i].

Today, we level up to 2D DP, where state requires two parameters: dp[i][j].

Why Do We Need 2D DP?

Simple answer: Some problems have state that depends on two independent factors.

Example 1: Two Sequences

Problem: Find the longest common subsequence of two strings.

State needs:

  • Position in first string: i
  • Position in second string: j

State definition: dp[i][j] = LCS of first i characters of string1 and first j characters of string2

Can't use 1D: You need to track progress in both strings simultaneously.

Example 2: Grid Navigation

Problem: Count paths from top-left to bottom-right in a grid.

State needs:

  • Current row: i
  • Current column: j

State definition: dp[i][j] = number of paths to reach cell (i, j)

Can't use 1D: Position requires both row and column.

Example 3: Knapsack with Constraints

Problem: Maximum value using first i items with weight limit j.

State needs:

  • Items considered so far: i
  • Remaining weight capacity: j

State definition: dp[i][j] = max value using first i items with capacity j

Can't use 1D: Decision depends on both which items you've seen and how much capacity remains.

When to Use 1D vs 2D

Use 1D when state depends on one factor:

  • Position in one sequence
  • Amount of money
  • Number of stairs
  • Single index

Use 2D when state depends on two factors:

  • Positions in two sequences (strings, arrays)
  • Position in a grid (row and column)
  • Items vs capacity
  • Two independent constraints

The Cost of Adding Dimensions

1D DP:

  • State space: O(n)
  • Time complexity: Usually O(n) or O(n × k)
  • Space complexity: O(n) (or O(1) with optimization)

2D DP:

  • State space: O(n × m)
  • Time complexity: Usually O(n × m) or O(n × m × k)
  • Space complexity: O(n × m) (or O(m) with row-by-row optimization)

Adding a dimension multiplies complexity!

For n = m = 1000:

  • 1D: 1,000 states
  • 2D: 1,000,000 states (1000× more!)

This matters for:

  • Memory usage
  • Computation time
  • Algorithm feasibility

Common 2D DP Patterns

Pattern 1: Two Sequences

Comparing or aligning two sequences.

Examples:

  • Longest Common Subsequence
  • Edit Distance
  • Longest Common Substring
  • Sequence Alignment

State: dp[i][j] relates to prefixes of both sequences

Recurrence: Usually considers matching or not matching current elements

Pattern 2: Grid Traversal

Navigating a 2D grid with constraints.

Examples:

  • Unique Paths
  • Minimum Path Sum
  • Dungeon Game
  • Cherry Pickup

State: dp[i][j] = value at position (i, j)

Recurrence: Usually from neighbors (up, left, diagonal)

Pattern 3: Knapsack Variants

Selecting items with multiple constraints.

Examples:

  • 0/1 Knapsack
  • Subset Sum
  • Partition Equal Subset Sum
  • Target Sum

State: dp[i][j] = optimal value using first i items with constraint j

Recurrence: Take item or leave it

Pattern 4: Game Theory

Optimal play for two players.

Examples:

  • Stone Game
  • Predict the Winner

State: dp[i][j] = optimal score for subproblem [i, j]

Recurrence: Minimax optimization

How 2D DP Extends 1D Principles

The fundamentals don't change!

Same principles apply:

  1. Define state clearly: Now with two indices instead of one
  2. Identify base cases: Usually edges of the 2D table
  3. Find recurrence relation: Now considering 2D neighbors
  4. Determine computation order: Fill table in dependency order
  5. Implement and optimize: Space optimization still possible

What's different:

  • Nested loops: Need two loops to fill the table
  • More base cases: Initialize entire row/column instead of single values
  • Harder to visualize: 2D table instead of 1D array
  • More complex dependencies: Multiple previous cells contribute

Visualization: 1D vs 2D

1D DP (Fibonacci):

dp[0] → dp[1] → dp[2] → dp[3] → dp[4] → dp[5]

Linear progression, each cell depends on previous 1-2 cells.

2D DP (Grid Paths):

    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
i=3  1    4   10   20

Each cell depends on cell above and cell to the left.

The table is a grid, not a line!

Problems We'll Solve Today

We'll work through four classic 2D DP problems:

1. Unique Paths

Type: Grid traversal

Why it's important: Introduces 2D state in the simplest context.

2. Longest Common Subsequence (LCS)

Type: Two sequences

Why it's important: Foundation for many sequence comparison algorithms.

3. Edit Distance

Type: Two sequences

Why it's important: Real-world application in spell check, DNA comparison, diff tools.

4. 0/1 Knapsack

Type: Selection with constraints

Why it's important: Classic optimization problem with countless variations.

Each teaches a different 2D pattern and builds problem-solving skills.

The Mindset Shift

Moving from 1D to 2D requires thinking in matrices instead of arrays.

Questions to ask yourself:

  • What two factors determine my state?
  • How do I initialize the first row and column?
  • Which cells does dp[i][j] depend on?
  • In what order should I fill the table?

The good news: If you mastered 1D DP, 2D is just more of the same principles applied to a grid.

Let's begin by learning how to set up 2D DP tables properly.