Module 24 · Dynamic Programming II: Grids, Knapsack, and Strings

232. Minimum Path Sum

Foundation · Download this solution · All solutions and shared helpers

Problem

Return the minimum sum of visited cell values on a right/down path from the top-left to the bottom-right of a rectangular integer grid. Include both endpoints. Values may be negative because movement is acyclic. Return None for an empty grid or an empty row. Do not mutate the grid.

Examples

Example 1

min_path_sum([[1,3,1],[1,5,1],[4,2,1]])
=> 7

The cheapest route follows the top row and then the right column.

Example 2

min_path_sum([[2,-5],[3,1]])
=> -2

Negative cells are valid in this acyclic movement graph.

Example 3

min_path_sum([])
=> None

No endpoint-to-endpoint path exists.

Reveal the worked solution and reasoning

Why this mechanism works

Replace path counting's sum over alternatives with a minimum over costs. The final move must come from above or left, then pay the current cell. Use infinity for absent predecessors so a boundary cannot take a nonexistent free route. Seed the origin with its actual value.

State and boundaries

dp[r][c] is the cheapest cost including cell (r,c). Both candidate predecessor states are already complete in row-major order.

Protocol

Handle empty input.
Initialize a cost table and set the origin.
For each other cell read top/left costs, using infinity when absent.
Add the current cell to their minimum.
Return the destination cost.

Visualization

grid:       best costs:
1 3 1       1 4 5
1 5 1       2 7 6
4 2 1       6 8 7

Python implementation

def min_path_sum(grid):
    if not grid or not grid[0]:
        return None
    rows, cols = len(grid), len(grid[0])
    dp = [[0] * cols for _ in range(rows)]
    dp[0][0] = grid[0][0]
    for r in range(rows):
        for c in range(cols):
            if r == c == 0:
                continue
            top = dp[r - 1][c] if r else float('inf')
            left = dp[r][c - 1] if c else float('inf')
            dp[r][c] = grid[r][c] + min(top, left)
    return dp[-1][-1]

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

min_path_sum([[1,3,1],[1,5,1],[4,2,1]])

L2 min_path_sum: if not grid or not grid[0]:
grid=[[1, 3, 1], [1, 5, 1], [4, 2, 1]]

L4 min_path_sum: rows, cols = len(grid), len(grid[0])
grid=[[1, 3, 1], [1, 5, 1], [4, 2, 1]]; rows=3; cols=3

L5 min_path_sum: dp = [[0] * cols for _ in range(rows)]
grid=[[1, 3, 1], [1, 5, 1], [4, 2, 1]]; rows=3; cols=3; _=0

L5 min_path_sum: dp = [[0] * cols for _ in range(rows)]
grid=[[1, 3, 1], [1, 5, 1], [4, 2, 1]]; rows=3; cols=3; _=1

L5 min_path_sum: dp = [[0] * cols for _ in range(rows)]
grid=[[1, 3, 1], [1, 5, 1], [4, 2, 1]]; rows=3; cols=3; _=2

L5 min_path_sum: dp = [[0] * cols for _ in range(rows)]
grid=[[1, 3, 1], [1, 5, 1], [4, 2, 1]]; rows=3; cols=3; dp=[[0, 0, 0], [0, 0, 0], [0, 0, 0]]

L6 min_path_sum: dp[0][0] = grid[0][0]
grid=[[1, 3, 1], [1, 5, 1], [4, 2, 1]]; rows=3; cols=3; dp=[[1, 0, 0], [0, 0, 0], [0, 0, 0]]

L7 min_path_sum: for r in range(rows):
grid=[[1, 3, 1], [1, 5, 1], [4, 2, 1]]; rows=3; cols=3; dp=[[1, 0, 0], [0, 0, 0], [0, 0, 0]]; r=0

... 30 intermediate state changes omitted ...

L8 min_path_sum: for c in range(cols):
grid=[[1, 3, 1], [1, 5, 1], [4, 2, 1]]; rows=3; cols=3; dp=[[1, 4, 5], [2, 7, 6], [6, 8, 0]]; r=2; c=2; top=7; left=6

L11 min_path_sum: top = dp[r - 1][c] if r else float('inf')
grid=[[1, 3, 1], [1, 5, 1], [4, 2, 1]]; rows=3; cols=3; dp=[[1, 4, 5], [2, 7, 6], [6, 8, 0]]; r=2; c=2; top=6; left=6

L12 min_path_sum: left = dp[r][c - 1] if c else float('inf')
grid=[[1, 3, 1], [1, 5, 1], [4, 2, 1]]; rows=3; cols=3; dp=[[1, 4, 5], [2, 7, 6], [6, 8, 0]]; r=2; c=2; top=6; left=8

L13 min_path_sum: dp[r][c] = grid[r][c] + min(top, left)
grid=[[1, 3, 1], [1, 5, 1], [4, 2, 1]]; rows=3; cols=3; dp=[[1, 4, 5], [2, 7, 6], [6, 8, 7]]; r=2; c=2; top=6; left=8

Result: 7. The cheapest route follows the top row and then the right column.

min_path_sum([[2,-5],[3,1]])

L2 min_path_sum: if not grid or not grid[0]:
grid=[[2, -5], [3, 1]]

L4 min_path_sum: rows, cols = len(grid), len(grid[0])
grid=[[2, -5], [3, 1]]; rows=2; cols=2

L5 min_path_sum: dp = [[0] * cols for _ in range(rows)]
grid=[[2, -5], [3, 1]]; rows=2; cols=2; _=0

L5 min_path_sum: dp = [[0] * cols for _ in range(rows)]
grid=[[2, -5], [3, 1]]; rows=2; cols=2; _=1

L5 min_path_sum: dp = [[0] * cols for _ in range(rows)]
grid=[[2, -5], [3, 1]]; rows=2; cols=2; dp=[[0, 0], [0, 0]]

L6 min_path_sum: dp[0][0] = grid[0][0]
grid=[[2, -5], [3, 1]]; rows=2; cols=2; dp=[[2, 0], [0, 0]]

L7 min_path_sum: for r in range(rows):
grid=[[2, -5], [3, 1]]; rows=2; cols=2; dp=[[2, 0], [0, 0]]; r=0

L8 min_path_sum: for c in range(cols):
grid=[[2, -5], [3, 1]]; rows=2; cols=2; dp=[[2, 0], [0, 0]]; r=0; c=0

... 9 intermediate state changes omitted ...

L8 min_path_sum: for c in range(cols):
grid=[[2, -5], [3, 1]]; rows=2; cols=2; dp=[[2, -3], [5, 0]]; r=1; c=1; top=2; left=inf

L11 min_path_sum: top = dp[r - 1][c] if r else float('inf')
grid=[[2, -5], [3, 1]]; rows=2; cols=2; dp=[[2, -3], [5, 0]]; r=1; c=1; top=-3; left=inf

L12 min_path_sum: left = dp[r][c - 1] if c else float('inf')
grid=[[2, -5], [3, 1]]; rows=2; cols=2; dp=[[2, -3], [5, 0]]; r=1; c=1; top=-3; left=5

L13 min_path_sum: dp[r][c] = grid[r][c] + min(top, left)
grid=[[2, -5], [3, 1]]; rows=2; cols=2; dp=[[2, -3], [5, -2]]; r=1; c=1; top=-3; left=5

Result: -2. Negative cells are valid in this acyclic movement graph.

Why the solution is correct

Every route into a nonorigin cell has one of the two legal predecessor cells. Replacing its prefix with the cheapest route to that predecessor cannot increase cost, so the recurrence considers an optimum route. Negative values cause no cycle or repeated relaxation because coordinates only increase.

Time and space

O(R*C) time and O(R*C) auxiliary table space.

Common mistakes

Using zero for missing predecessors permits paths entering from outside the grid. Omitting the origin's value changes the cost contract.

Reasoning card

State: dp[r][c] is the cheapest cost including cell (r,c). Both candidate predecessor states are already complete in row-major order.

Invariant: Each state is the cheapest cost to reach its cell.

Decision to rehearse: Current cost equals cell value plus min(top,left).

Finish: Return the destination cost

Transfer exercise

Store the winning predecessor direction at each cell and reconstruct a minimum-cost route.