Minimum Path Sum

Problem Summary

Given an m x n grid filled with non-negative numbers, find a path from the top-left corner to the bottom-right corner that minimizes the sum of all numbers along the path. At any point you may move only either down or right. Both dimensions are between 1 and 200, and each cell value is between 0 and 200. Return the minimum possible path sum.

Techniques

Array
Dynamic Programming
Matrix

Solution

function minPathSum(grid: number[][]): number {
    const m = grid.length;
    const n = grid[0].length;
    const dp: number[][] = Array.from({ length: m }, () => Array(n).fill(0));

    dp[m - 1][n - 1] = grid[m - 1][n - 1];

    for (let i = m - 1; i >= 0; i--) {
        for (let j = n - 1; j >= 0; j--) {
            if (i === m - 1 && j === n - 1) {
                continue;
            }
            const down = i + 1 < m ? dp[i + 1][j] : Infinity;
            const right = j + 1 < n ? dp[i][j + 1] : Infinity;
            dp[i][j] = grid[i][j] + Math.min(down, right);
        }
    }

    return dp[0][0];
}