DP 8. Grid Unique Paths | Learn Everything about DP on Grids

Mastering Dynamic Programming (DP) on Grids (or 2D matrices) is a critical milestone for cracking technical interviews at top-tier tech companies. This chapter covers the foundational pattern of counting unique paths across an $m \times n$ grid, establishing a rigorous progression from pure recursion to memoization, tabulation, and finally, space optimization.

1. Why Do We Need DP on Grids? (Problem Statement & Status Quo)

When navigating standard 1D arrays or strings, we typically manage a single index ($i$). However, real-world data structures often extend into multi-dimensional spaces—such as a chessboard, a pixel matrix, or a map layout.

• The Objective: Given an $m \times n$ grid, start at the top-left cell Point A (0, 0) and find the total number of unique paths to reach the bottom-right cell Point B (m-1, n-1).
• Movement Constraints: You are only allowed to move Right or Down at any given step.
• The Core Challenge: Because you must explore all possible ways to reach the destination, a naive combinatorial approach quickly leads to overlapping subproblems and exponential time complexity. Dynamic programming ensures we solve each subproblem exactly once.

2. The Core Mental Model & Real-Life Analogy

Real-Life Analogy: Navigating City Blocks

Imagine you are standing at the top-left corner of a grid-like city layout (such as Manhattan) where streets run strictly North-South and East-West. You want to visit a friend's house at the exact opposite corner of the city. Because traffic laws or one-way systems only permit you to drive South or East, every valid journey is a unique sequence of downward and rightward turns. Counting all possible driving routes from your starting doorstep to your destination doorstep is mathematically identical to finding grid unique paths.

• Opposite Perspective (Backwards Induction): While we physically walk from (0,0) to (m-1, n-1), our recursive function evaluates things in reverse: it asks, "If I am standing at cell (i, j), how many ways did it take to get here from the start, or how many ways can I reach the end?" By working backwards from the destination, we cleanly define our state transitions.

3. The 3-Step Master Blueprint for 2D Grid DP

Whenever you encounter a 2D grid DP problem, strictly adhere to this three-step blueprint:

1. Express everything in terms of indexes (i, j): Instead of a single 1D index, use two indices where i represents the row number and j represents the column number.
2. Explore all paths / Do all stuffs: Write out every possible movement choice permitted by the problem (e.g., Up/Left when moving backwards, or Down/Right when moving forwards).
3. Accumulate results: If the problem asks to count ways, sum up the results of all recursive choices (return up + left). If it asks for min/max, take the min or max.

4. Step 1: Naive Recursive Solution

To count paths recursively, we define a function f(i, j) that represents the total number of unique paths to reach cell (i, j) from (0, 0). Working backwards from the destination (m-1, n-1) to (0, 0):

• Base Cases:
  • If i == 0 and j == 0, we have successfully hit the starting cell via a valid path. Return 1 (which counts as 1 valid path).
  • If i < 0 or j < 0, our path has crossed the matrix boundaries. Return 0 (this path is invalid).
• Choices: At any cell (i, j), we can arrive either from the cell directly above (i-1, j) or directly to the left (i, j-1).

Recursive Code Implementation

int f(int i, int j) {
    // Base Case 1: Reached the start point
    if (i == 0 && j == 0) return 1;
    
    // Base Case 2: Out of bounds
    if (i < 0 || j < 0) return 0;
    
    // Explore choices: move up and move left (backwards traversal)
    int up = f(i - 1, j);
    int left = f(i, j - 1);
    
    // Sum all ways
    return up + left;
}

• Time Complexity: $\mathcal{O}(2^{m \times n})$ — Exponential, because at every cell we branch into 2 recursive calls.
• Space Complexity: $\mathcal{O}(m + n)$ — Auxiliary recursion stack space proportional to the maximum path length.

5. Step 2: Memoized Solution (Top-Down DP)

If you draw out the recursion tree for a $3 \times 3$ matrix, you will quickly notice overlapping subproblems—the same cells (e.g., f(1, 1), f(0, 1)) are computed repeatedly across different branches.

Memoization Strategy

1. Declare a 2D DP array/vector of size m x n, initialized with -1.
2. Before computing f(i, j), check if dp[i][j] is already calculated. If yes, return it immediately.
3. Store the result in dp[i][j] before returning.

Memoized Code Implementation

int f(int i, int j, vector<vector<int>>& dp) {
    if (i == 0 && j == 0) return 1;
    if (i < 0 || j < 0) return 0;
    
    // Check if already computed
    if (dp[i][j] != -1) return dp[i][j];
    
    int up = f(i - 1, j, dp);
    int left = f(i, j - 1, dp);
    
    // Store and return
    return dp[i][j] = up + left;
}

• Time Complexity: $\mathcal{O}(m \times n)$ — Each state is computed exactly once.
• Space Complexity: $\mathcal{O}(m \times n)$ (for the 2D DP table) + $\mathcal{O}(m + n)$ (for the recursion stack space).

6. Step 3: Tabulation Solution (Bottom-Up DP)

Tabulation eliminates recursion overhead and stack space by building solutions iteratively from the "bottom" (base case) up to the target.

Tabulation Transformation Rules

1. Initialize the DP Table: Create a 2D array of size m x n.
2. Translate Base Cases: Set dp[0][0] = 1.
3. Convert Recursive Loops to For-Loops: Iterate through every row i from 0 to m-1 and every column j from 0 to n-1.
4. Safe Boundary Checks: Handle negative indices explicitly by checking if i > 0 and j > 0 before pulling values from dp[i-1][j] or dp[i][j-1].

Tabulated Code Implementation

int uniquePaths(int m, int n) {
    vector<vector<int>> dp(m, vector<int>(n, 0));
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            // Base case
            if (i == 0 && j == 0) {
                dp[i][j] = 1;
                continue;
            }
            
            int up = 0;
            int left = 0;
            
            // Collect paths from top if within bounds
            if (i > 0) up = dp[i - 1][j];
            
            // Collect paths from left if within bounds
            if (j > 0) left = dp[i][j - 1];
            
            dp[i][j] = up + left;
        }
    }
    return dp[m - 1][n - 1];
}

• Time Complexity: $\mathcal{O}(m \times n)$
• Space Complexity: $\mathcal{O}(m \times n)$ (completely eliminates stack space).

7. Step 4: Space-Optimized Solution (1D Array Optimization)

If you examine the tabulation recurrence:

Notice that to compute the current row i, we only require data from the previous row (i-1) and the current row's left element (j-1). We do not need the entire 2D grid history.

Space Optimization Strategy

• Maintain two 1D arrays of size n: prev (representing row i-1) and temp (representing the current row i).
• After completing a row, assign prev = temp before moving to the next row.

Space-Optimized Code Implementation

int uniquePathsSpaceOptimized(int m, int n) {
    vector<int> prev(n, 0);
    
    for (int i = 0; i < m; i++) {
        vector<int> temp(n, 0);
        for (int j = 0; j < n; j++) {
            if (i == 0 && j == 0) {
                temp[j] = 1;
                continue;
            }
            
            int up = 0;
            int left = 0;
            
            if (i > 0) up = prev[j];          // Value from previous row
            if (j > 0) left = temp[j - 1];    // Value from current row, previous column
            
            temp[j] = up + left;
        }
        prev = temp; // Move current row to prev for the next iteration
    }
    return prev[n - 1];
}

• Time Complexity: $\mathcal{O}(m \times n)$
• Space Complexity: $\mathcal{O}(n)$ — Reduced memory footprint down to a single row vector.

8. Comprehensive Comparison of Techniques

9. Summary and Key Takeaways

• Foundational Blueprint: Always follow the 3-step rule for DP on Grids: Express states as (i, j), explore all directional choices, and accumulate results based on the problem prompt.
• Backwards vs. Forwards: Traversing backwards from destination (m-1, n-1) to start (0, 0) simplifies base cases and aligns naturally with counting paths.
• Overlapping Subproblems: Grid traversals inherently revisit cells across multiple paths, making memoization or tabulation mandatory to avoid exponential time waste.
• Space Reduction Insight: Whenever a DP state depends exclusively on the immediate previous row or column, discard the 2D matrix in favor of 1D rolling vectors.
• Mathematical Alternative: While DP teaches general grid navigation (essential for handling obstacles and costs later), unique paths can also be solved in $\mathcal{O}(min(m, n))$ time using combinatorics: $\binom{m+n-2}{m-1}$.