Matrix DP | Engineering Interview Kit

Concept

Many Dynamic Programming problems take place directly on a 2D Matrix (Grid).

Unique Paths (LeetCode #62):
Problem: A robot is located at the top-left corner of an m x n grid. The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner. How many possible unique paths are there?

Because you can only move Down or Right, if you are standing on a random square, where did you come from?
You MUST have arrived from the square immediately Above you, or the square immediately to the Left.
Therefore, the total number of unique paths to reach your square is mathematically the sum of the paths from Above and Left!

dp[r][c] = dp[r-1][c] + dp[r][c-1]

Unique Paths Implementation

// Time Complexity: O(M * N)
// Space Complexity: O(M * N)

function uniquePaths(m: number, n: number): number {
    // Create the DP Matrix
    const dp = Array.from({ length: m }, () => new Array(n).fill(0));

    // Base Case: The top row and left column only have exactly 1 valid path 
    // (walking in a straight straight line)
    for (let r = 0; r < m; r++) dp[r][0] = 1;
    for (let c = 0; c < n; c++) dp[0][c] = 1;

    // Build the grid
    for (let r = 1; r < m; r++) {
        for (let c = 1; c < n; c++) {
            // Paths from Top + Paths from Left
            dp[r][c] = dp[r - 1][c] + dp[r][c - 1];
        }
    }

    return dp[m - 1][n - 1]; // The bottom-right corner
}

State Reduction: Because dp[r][c] only looks at the row above it, you can optimize the Space Complexity to $O(N)$ by only storing two 1D arrays (previousRow and currentRow).

Minimum Path Sum (LeetCode #64)

Problem: Given an m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path. You can only move down or right.

This is the exact same problem! But instead of adding the paths together, we are taking the Math.min(), and we add the cost of the square we are standing on.

dp[r][c] = cost[r][c] + Math.min(dp[r-1][c], dp[r][c-1])

function minPathSum(grid: number[][]): number {
    const rows = grid.length;
    const cols = grid[0].length;

    // Mutate the original grid to save space! (In-Place DP)
    
    // Seed the first column
    for (let r = 1; r < rows; r++) {
        grid[r][0] += grid[r - 1][0];
    }
    
    // Seed the first row
    for (let c = 1; c < cols; c++) {
        grid[0][c] += grid[0][c - 1];
    }

    // Process the inner matrix
    for (let r = 1; r < rows; r++) {
        for (let c = 1; c < cols; c++) {
            grid[r][c] += Math.min(grid[r - 1][c], grid[r][c - 1]);
        }
    }

    return grid[rows - 1][cols - 1];
}

Interview Questions

Q: In minPathSum, you mutated the input grid array. Is that acceptable?
A: In algorithmic interviews, In-Place DP (mutating the input grid) is the absolute holy grail because it drops the Space Complexity to a flawless $O(1)$ . However, you should always politely ask the interviewer: “Is it acceptable to mutate the input array to achieve $O(1)$ space, or would you prefer I allocate a new DP array?” In real-world software engineering, mutating input parameters is often forbidden because it destroys the original data.

Q: What if the robot can move in all 4 directions (Up, Down, Left, Right)? Can we use DP?
A: No! Dynamic Programming strictly requires a Directed Acyclic Graph (DAG). If you can move Up and Down, you create an infinite circular dependency. You can step Down to Row 2, and step Up to Row 1, creating an infinite loop. The Recurrence Relation dp[r][c] will try to check dp[r+1][c], which hasn’t been calculated yet, completely breaking the matrix logic. For 4-directional movement, you MUST use Graph Traversal (BFS for shortest path, DFS for all paths).