Dynamic Programming • 2D Grids

Minimum Path Sum

Find a path from top-left to bottom-right in a grid, moving only down or right, which minimizes the sum of all numbers along its path.

Try Interactive Simulator

Overview

This is a variation of Grid Unique Paths, but instead of counting ways, we want to optimize a cost function (the sum of values).

The Logic

Since you can only move down or right, the cell `(r, c)` can only be entered from `(r-1, c)` (top) or `(r, c-1)` (left). To minimize the total cost at `(r, c)`, you must choose the minimum of those two entry paths.

Base Cases

The top boundary can only be reached by moving right. The left boundary can only be reached by moving down. We prefill these to avoid out-of-bounds checks in the main loop.

Space Optimization

Since we only look at the current row and the row above it, we can optimize space to O(N) by keeping just two 1D arrays, or mutating the original grid.

Code Tracker

:::

1for (let r = 0; r < R; r++) {

2 for (let c = 0; c < C; c++) {

3 if (r === 0 && c === 0) dp[r][c] = grid[r][c];

4 else if (r === 0) dp[r][c] = dp[r][c-1] + grid[r][c];

5 else if (c === 0) dp[r][c] = dp[r-1][c] + grid[r][c];

6 else dp[r][c] = Math.min(dp[r-1][c], dp[r][c-1]) + grid[r][c];

7 }

8}