AlgoMaster Logo

Minimum Path Sum

mediumFrequency7 min readUpdated June 23, 2026

Understanding the Problem

We have a grid of non-negative integers with m rows and n columns. Starting from the top-left cell (0, 0), we need to reach the bottom-right cell (m - 1, n - 1). At each step, we can only move right or down. Among all possible paths from start to destination, we want the one whose cell values add up to the smallest total.

This is closely related to the "Unique Paths" problem, but instead of counting paths, we are optimizing over them. The restricted movement (only right or down) means there are no cycles, which gives the acyclic subproblem structure that dynamic programming relies on. Every path makes exactly (m - 1) down moves and (n - 1) right moves, so every path visits the same number of cells: m + n - 1. The question is which combination of cells gives us the smallest sum.

The minimum-cost path to any cell (i, j) must arrive from either (i - 1, j) or (i, j - 1), whichever offers the cheaper route. This optimal substructure property is what makes dynamic programming applicable.

Key Constraints:

  • 1 <= m, n <= 200 → The grid has at most 200 x 200 = 40,000 cells. An O(m * n) solution runs in well under a millisecond. Anything exponential is out.
  • 0 <= grid[i][j] <= 200 → All values are non-negative. This means we never benefit from taking a longer path. The minimum sum fits easily in an integer: worst case is 200 * (200 + 200 - 1) = 79,800.

Approach 1: Recursion (Brute Force)

Intuition

We can define the answer recursively. The minimum path sum to cell (i, j) is grid[i][j] plus the cheaper of the two ways to reach it: the best path to (i - 1, j) or the best path to (i, j - 1).

The base case is the top-left cell (0, 0), where the cost is grid[0][0]. Going out of bounds (negative row or column) returns infinity, since that is not a valid path.

This is correct but slow. The recursion tree branches into two at every cell, and the same subproblems get solved over and over.

Algorithm

  1. Define a recursive function minCost(i, j) that returns the minimum path sum from (0, 0) to (i, j).
  2. Base case: if i == 0 and j == 0, return grid[0][0].
  3. If i < 0 or j < 0, return a very large number (infinity).
  4. Return grid[i][j] + min(minCost(i - 1, j), minCost(i, j - 1)).
  5. Call minCost(m - 1, n - 1).

Example Walkthrough

1Start: recursive calls from (2,2) branch to (1,2) and (2,1)
0
1
2
0
1
3
1
1
1
5
1
2
4
2
target
1
1/3

Code

There are only m * n distinct subproblems, but the recursion solves each one many times. The next approach computes the minimum cost for each cell exactly once, building up from the top-left corner.

Approach 2: Dynamic Programming (2D Table)

Intuition

Instead of recursing backward and recomputing the same cells, we build the answer forward. We create a 2D table dp where dp[i][j] is the minimum path sum from (0, 0) to (i, j).

Since the only ways to reach (i, j) are from above or from the left, the recurrence is:

dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1])

The first row and first column are the base cases. A cell in the first row can only be reached by moving right from the start, so dp[0][j] is the prefix sum of the first row. A cell in the first column can only be reached by moving down, so dp[i][0] is the prefix sum of the first column.

Algorithm

  1. Create a 2D array dp of size m x n.
  2. Set dp[0][0] = grid[0][0].
  3. Fill the first row: dp[0][j] = dp[0][j - 1] + grid[0][j].
  4. Fill the first column: dp[i][0] = dp[i - 1][0] + grid[i][0].
  5. For each remaining cell (i, j): set dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1]).
  6. Return dp[m - 1][n - 1].

Example Walkthrough

1Initialize: dp[0][0] = grid[0][0] = 1
0
1
2
0
start=1
1
0
0
1
0
0
0
2
0
0
0
1/8

Code

The time complexity is optimal, but the DP table uses O(m * n) extra space. Filling row i only reads row i - 1 and the cell to the left in the current row, so the next approach replaces the full table with a single 1D array updated row by row.

Approach 3: Dynamic Programming (Space-Optimized 1D)

Intuition

Since each row of the DP table only depends on the row directly above it, we can compress the 2D table into a single 1D array of length n. When we process columns left to right, dp[j] still holds the value from the previous row (the "from above" value) because we have not updated it yet, and dp[j - 1] holds the current row's value (the "from left" value) because we just updated it.

The update becomes: dp[j] = grid[i][j] + min(dp[j], dp[j - 1])

Algorithm

  1. Create a 1D array dp of size n.
  2. Initialize dp with the prefix sums of the first row.
  3. For each row i from 1 to m - 1:
    • Update dp[0] = dp[0] + grid[i][0] (first column, can only come from above).
    • For each column j from 1 to n - 1: update dp[j] = grid[i][j] + min(dp[j], dp[j - 1]).
  4. Return dp[n - 1].

Example Walkthrough

1Initialize dp with first row prefix sums: [1, 4, 5]
0
1
1
4
2
5
1/8

Code