Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumtwo-dimensional-dp

Minimum Path Sum

Problem (restated)

m×n grid of non-negatives. Path from top-left to bottom-right (right/down only). Minimize sum.

Intuition

dp[i][j] = grid + min(from top, from left). Fill first row/col then rest.

Approaches

Grid DP in-place

Unverified

Time O(mn)Space O(1) extra

Idea. can mutate grid: grid[i][j] += min(up, left).

Walkthrough. [[1,3,1],[1,5,1],[4,2,1]] → 7 (1→3→1→1→1).

Trade-offs. Same family as unique paths; add cost.

Solution

export function minPathSum(grid: number[][]): number {
  const m = grid.length, n = grid[0]!.length;
  for (let i = 1; i < m; i++) grid[i]![0]! += grid[i - 1]![0]!;
  for (let j = 1; j < n; j++) grid[0]![j]! += grid[0]![j - 1]!;
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      grid[i]![j]! += Math.min(grid[i - 1]![j]!, grid[i]![j - 1]!);
    }
  }
  return grid[m - 1]![n - 1]!;
}

export function minPathSum(grid: number[][]): number {
  const m = grid.length, n = grid[0]!.length;
  for (let i = 1; i < m; i++) grid[i]![0]! += grid[i - 1]![0]!;
  for (let j = 1; j < n; j++) grid[0]![j]! += grid[0]![j - 1]!;
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      grid[i]![j]! += Math.min(grid[i - 1]![j]!, grid[i]![j - 1]!);
    }
  }
  return grid[m - 1]![n - 1]!;
}

Template connection

Two-dimensional DP grid states.

Reflection

Add the cell to min(above, left). The first row accumulates only from the left. The first column accumulates only from above.
Writing into the grid erases the input. Copy the grid when the caller still needs the original numbers.
One cell is itself. Values are non-negative. A single row is only horizontal.