Skip to content
ΣDSA Patterns
Menu
PatternsProblemsTemplatesRoadmapResourcesReviewsAbout
Language
EnglishTürkçe

Two-Dimensional DP

Guide 3 of 6 · Path 3 of 6

← PreviousNext →

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

Tested only
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