Command Palette

Search for a command to run...

Setting Up 2D DP Tables

Before solving 2D DP problems, we need to master the mechanics of setting up and filling 2D tables.

This is crucial: A single indexing mistake can derail your entire solution!

Array Declaration and Sizing

For a 2D DP problem with parameters i (0 to n) and j (0 to m):

Java
int[][] dp = new int[n + 1][m + 1];

Why +1?

Same reason as 1D: To naturally use indices 0 through n (and 0 through m).

Example: String comparison with length n=3 and m=4

Java
// Compare strings of length 3 and 4
int[][] dp = new int[4][5];  // [n+1][m+1]

Alternative: Use n and m directly if you're careful with index mapping. But +1 is clearer and less error-prone.

Understanding the Indices

Convention: dp[i][j] typically means:

First index (i): Row (often represents position in first sequence or row in grid)

Second index (j): Column (often represents position in second sequence or column in grid)

Visualization:

        j=0  j=1  j=2  j=3  j=4
    i=0 [  ] [  ] [  ] [  ] [  ]
    i=1 [  ] [  ] [  ] [  ] [  ]
    i=2 [  ] [  ] [  ] [  ] [  ]
    i=3 [  ] [  ] [  ] [  ] [  ]

Reading: dp[2][3] is row 2, column 3

Initializing the Table

Three common patterns:

Pattern 1: Zero Initialization

Default in Java: All elements start at 0

Java
int[][] dp = new int[n + 1][m + 1];
// Already initialized to 0

Use when: Zero is a valid default (counting problems, accumulation)

Pattern 2: First Row and Column

Common in sequence comparison and grid problems:

Java
// Initialize first row
for (int j = 0; j <= m; j++) {
    dp[0][j] = baseValue(j);
}

// Initialize first column
for (int i = 0; i <= n; i++) {
    dp[i][0] = baseValue(i);
}

Example: Edit Distance

Java
// dp[0][j] = cost of inserting j characters
for (int j = 0; j <= m; j++) {
    dp[0][j] = j;
}

// dp[i][0] = cost of deleting i characters
for (int i = 0; i <= n; i++) {
    dp[i][0] = i;
}

Result:

        j=0  j=1  j=2  j=3
    i=0  0    1    2    3
    i=1  1    ?    ?    ?
    i=2  2    ?    ?    ?
    i=3  3    ?    ?    ?

Base cases (row 0 and column 0) are set, now fill the rest.

Pattern 3: Sentinel Values

For minimization/maximization problems:

Java
// Initialize all to infinity (minimization)
int[][] dp = new int[n + 1][m + 1];
for (int i = 0; i <= n; i++) {
    Arrays.fill(dp[i], Integer.MAX_VALUE);
}

// Then set actual base cases
dp[0][0] = 0;

Use when: Need to distinguish "computed" from "not yet computed" or "impossible"

Determining Iteration Order

Critical question: Which cells does dp[i][j] depend on?

Most common dependency pattern:

dp[i][j] depends on:
  - dp[i-1][j]     (cell above)
  - dp[i][j-1]     (cell to the left)
  - dp[i-1][j-1]   (cell diagonally above-left)

Visualization:

    [i-1][j-1]  [i-1][j]
    [i][j-1]    [i][j]    ← Computing this cell

Iteration order: Left-to-right, top-to-bottom

Java
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        // Compute dp[i][j] from dp[i-1][j-1], dp[i-1][j], dp[i][j-1]
    }
}

Why this works: By the time we compute dp[i][j], all cells it depends on (above and to the left) have already been computed.

Trace for 4×5 table:

Order of computation:

Base: Row 0 and Column 0 initialized first

Then:
  1 →  2 →  3 →  4
  5 →  6 →  7 →  8
  9 → 10 → 11 → 12

Cell 1 depends on row 0 and column 0 (already done). Cell 2 depends on row 0 and cell 1 (already done). And so on...

Different Dependency Patterns

Pattern 1: Grid Paths (Only From Above and Left)

Recurrence:

Java
dp[i][j] = dp[i-1][j] + dp[i][j-1];

Dependencies:

    [i-1][j]
    [i][j-1]  [i][j]

Iteration: Left-to-right, top-to-bottom ✓

Pattern 2: Sequence Comparison (All Three Directions)

Recurrence:

Java
dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1] + match);

Dependencies:

    [i-1][j-1]  [i-1][j]
    [i][j-1]    [i][j]

Iteration: Left-to-right, top-to-bottom ✓

Pattern 3: Diagonal Dependencies

Some problems look diagonally:

    [i-1][j+1]
    [i][j]

Iteration: Might need different order! (Right-to-left in inner loop, or diagonal sweeps)

Rare: Most standard 2D DP uses left-to-right, top-to-bottom.

Index Boundary Checks

Always verify:

Java
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        // Safe: i-1 >= 0, j-1 >= 0
        dp[i][j] = f(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]);
    }
}

Why start at 1? Base cases (row 0, column 0) are already set. Starting at 1 avoids out-of-bounds on i-1 and j-1.

If you must start at 0:

Java
for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
        if (i == 0 || j == 0) {
            // Handle base case
        } else {
            // Normal recurrence
        }
    }
}

More verbose, but sometimes necessary.

Common Mistakes

Mistake 1: Wrong Array Size

Java
// WRONG: Too small!
int[][] dp = new int[n][m];
// Can't access dp[n][m] if needed!

// CORRECT:
int[][] dp = new int[n + 1][m + 1];

Mistake 2: Forgetting to Initialize Base Cases

Java
// WRONG: No base case!
int[][] dp = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        dp[i][j] = dp[i-1][j] + dp[i][j-1];
    }
}
// dp[1][1] will be 0 + 0 = 0, but should it be?

// CORRECT:
int[][] dp = new int[n + 1][m + 1];
// Set base cases first
dp[0][0] = 1;
for (int i = 1; i <= n; i++) dp[i][0] = 1;
for (int j = 1; j <= m; j++) dp[0][j] = 1;
// Then fill rest

Mistake 3: Wrong Iteration Order

Java
// If dp[i][j] depends on dp[i+1][j] and dp[i][j+1]:
// WRONG: This computes cells before their dependencies!
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        dp[i][j] = dp[i+1][j] + dp[i][j+1];  // Not computed yet!
    }
}

// CORRECT: Iterate backwards
for (int i = n - 1; i >= 0; i--) {
    for (int j = m - 1; j >= 0; j--) {
        dp[i][j] = dp[i+1][j] + dp[i][j+1];  // Already computed!
    }
}

Mistake 4: Swapping i and j

Java
// Inconsistent use of i and j
dp[i][j] = dp[j-1][i] + dp[i][j-1];  // Confusing!

Best practice: Be consistent. Usually i = row, j = column.

Template for 2D DP

Java
public int solve2DDP(int n, int m) {
    // Step 1: Create DP table
    int[][] dp = new int[n + 1][m + 1];

    // Step 2: Initialize base cases
    // Row 0
    for (int j = 0; j <= m; j++) {
        dp[0][j] = baseCase0(j);
    }
    // Column 0
    for (int i = 0; i <= n; i++) {
        dp[i][0] = baseCase1(i);
    }

    // Step 3: Fill table using recurrence
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp[i][j] = recurrence(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]);
        }
    }

    // Step 4: Return result
    return dp[n][m];
}

Adapt this template to specific problems by:

  • Changing base case initialization
  • Changing recurrence relation
  • Changing what you return (might not be dp[n][m])

Printing the Table (Debugging)

Helpful for understanding and debugging:

Java
public static void printTable(int[][] dp) {
    for (int i = 0; i < dp.length; i++) {
        for (int j = 0; j < dp[0].length; j++) {
            System.out.printf("%4d ", dp[i][j]);
        }
        System.out.println();
    }
}

Example output:

   0    1    2    3    4
   1    2    3    4    5
   2    3    4    5    6
   3    4    5    6    7

Use this: After computing base cases, after filling table, to verify correctness.

Key Takeaways

Setting up 2D DP tables:

  • Use int[n+1][m+1] for natural indexing
  • Initialize base cases (first row and column) before filling table
  • Determine dependency pattern (which cells does dp[i][j] need?)
  • Iterate in order that ensures dependencies are computed first
  • Most common: left-to-right, top-to-bottom (i from 1 to n, j from 1 to m)

The foundation of 2D DP:

  • Correct setup prevents bugs
  • Clear indexing prevents confusion
  • Proper iteration order ensures correctness

Now that we understand the mechanics, let's solve actual problems!

What's Next

We'll apply this setup to our first 2D DP problem: Unique Paths, a clean grid traversal problem that demonstrates the basics of 2D DP without additional complexity.