2D Dynamic Programming Pattern

The 2D Dynamic Programming pattern solves optimization problems involving two independent decision parameters (e.g. grids, two sequences, or range boundaries) by storing solutions to overlapping subproblems in a 2D matrix.

Recognition Signals

You should consider this pattern if you see any of the following cues in the problem description:

• The problem involves navigating a 2D grid with directional constraints (e.g. “can only move down and right”).
• The problem involves comparing or aligning two separate strings or sequences (e.g. Longest Common Subsequence, Edit Distance).
• The state at coordinate (r, c) depends directly on adjacent completed states (e.g. (r-1, c), (r, c-1), or (r-1, c-1)).
• The decision requires tracking two variables at each step (e.g. Knapsack: index and remaining capacity).

How It Works

Instead of checking all paths or alignments recursively (which runs in exponential O(2^(m+n)) time), you cache solutions in a 2D table dp[rows][cols]:

• Bottom-Up Tabulation: Initialize a 2D matrix with base cases (e.g. first row and column). Traverse cell-by-cell, filling each slot based on the subproblem values from its neighbors.
• Space Optimization: Because the calculations for row r only reference cells in row r and row r - 1, you can reduce memory from O(m * n) to O(n) by only keeping two rows (or a single row updated in-place).

For example, to find the number of unique paths in an m x n grid:

1. Initialize a 2D grid: dp[m][n].
2. Base cases: set dp[r][0] = 1 and dp[0][c] = 1 (only 1 way to go straight down or right).
3. State transition: dp[r][c] = dp[r - 1][c] + dp[r][c - 1] (paths from above + paths from left).
4. Return dp[m - 1][n - 1].

Complexity, With Caveats

• Time Complexity: O(m * n) where m and n are the dimensions of the state matrix. We calculate the value of each cell exactly once in constant time.
• Space Complexity: O(m * n) to store the 2D state table. This can be optimized to O(n) space (where n is the smaller dimension) by storing only the previous and current row/column.

Minimal Code Template

public class DynamicProgramming2DTemplate {
    // Bottom-Up Tabulation (Unique Paths)
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];

        // base cases: first row and column
        for (int r = 0; r < m; r++) dp[r][0] = 1;
        for (int c = 0; c < n; c++) dp[0][c] = 1;

        for (int r = 1; r < m; r++) {
            for (int c = 1; c < n; c++) {
                dp[r][c] = dp[r - 1][c] + dp[r][c - 1]; // paths from above + left
            }
        }
        return dp[m - 1][n - 1];
    }

    // Space Optimized Bottom-Up (O(n) Space)
    public int uniquePathsOptimized(int m, int n) {
        int[] dp = new int[n];
        for (int c = 0; c < n; c++) dp[c] = 1; // base case row

        for (int r = 1; r < m; r++) {
            for (int c = 1; c < n; c++) {
                dp[c] = dp[c] + dp[c - 1]; // updated in-place using left and old values
            }
        }
        return dp[n - 1];
    }
}

# Bottom-Up Tabulation (Unique Paths)
def unique_paths(m: int, n: int) -> int:
    dp = [[1] * n for _ in range(m)]

    for r in range(1, m):
        for c in range(1, n):
            dp[r][c] = dp[r - 1][c] + dp[r][c - 1]  # paths from above + left

    return dp[m - 1][n - 1]


# Space Optimized Bottom-Up (O(n) Space)
def unique_paths_optimized(m: int, n: int) -> int:
    dp = [1] * n

    for r in range(1, m):
        for c in range(1, n):
            dp[c] = dp[c] + dp[c - 1]  # updated in-place using left and old values

    return dp[n - 1]

#include <vector>

class DynamicProgramming2DTemplate {
public:
    // Bottom-Up Tabulation (Unique Paths)
    int uniquePaths(int m, int n) {
        std::vector<std::vector<int>> dp(m, std::vector<int>(n, 1));

        for (int r = 1; r < m; r++) {
            for (int c = 1; c < n; c++) {
                dp[r][c] = dp[r - 1][c] + dp[r][c - 1]; // paths from above + left
            }
        }
        return dp[m - 1][n - 1];
    }

    // Space Optimized Bottom-Up (O(n) Space)
    int uniquePathsOptimized(int m, int n) {
        std::vector<int> dp(n, 1);

        for (int r = 1; r < m; r++) {
            for (int c = 1; c < n; c++) {
                dp[c] = dp[c] + dp[c - 1]; // updated in-place using left and old values
            }
        }
        return dp[n - 1];
    }
};

Where This Pattern Falls Short

• Exponential state growth: If the state transition depends on additional dynamic bounds (e.g. traveling salesman route sequences), the dimensions grow beyond 2D, causing time and memory to explode exponentially (O(2ⁿ * n²)).
• Unreachable states: If the grid contains roadblocks that make most cells unreachable, filling the entire table bottom-up performs many redundant calculations. Top-down memoization is preferred because it only visits reachable states.

Related Patterns, Compared

• 1D Dynamic Programming: choose this instead when the subproblems can be indexed along a single sequence dimension, saving memory and complexity.
• Backtracking: choose this instead when you must generate the actual paths or combinations themselves rather than finding a single optimized statistic (count, max, min).

Frequently Asked Questions

How do we decide the size of our DP array? The size is determined by the range of variables. If you have row index r (0 to m-1) and column index c (0 to n-1), you declare a table of size m x n.

When is top-down memoization better than bottom-up tabulation in 2D? Top-down is better when the total state space is very large but only a small portion is actually visited during the search, as tabulation will waste time computing every single cell in the grid.

What does this pattern test in interviews? It tests your ability to model complex multi-parameter decisions, write nested loop indices correctly, and optimize 2D array space allocations.