Minimum Path Sum

Problem statement

You get an m × n grid of non-negative integers. Start at the top-left, walk to the bottom-right, moving only right or down. Return the smallest sum of numbers on a path. You must include both ends.

Example:

Input:

grid = [[1, 3, 1],
        [1, 5, 1],
        [4, 1, 1]]

Expected output:

7

Why: 1 → 3 → 1 → 1 → 1. The path through 5 is heavier.

Practice on LeetCode: Minimum Path Sum

What we are minimizing

This is the same grid walk as Unique Paths. The question changed. Unique Paths counts routes. This one prices them.

The cheapest path from a cell to the end is that cell’s value, plus the cheaper of the cell below and the cell to the right. The end cell costs only itself — there is nowhere left to go.

from(i, j) = grid[i][j] + min(from(i+1, j), from(i, j+1))
from(m-1, n-1) = grid[m-1][n-1]

Fill the example from the end:

7 6 3
7 7 2
6 2 1

Top-left is 7.

A missing neighbor is not a path. The helper seeds down and right at math.MaxInt, then only overwrites a direction that exists. min then ignores the wall.

Why not try every path

Same branch as Unique Paths: two choices per cell, the same cell asked from many prefixes. Without a table the tree is exponential. There are only m · n cells. Remember the cheapest finish from each one.

Bottom-up writes the same recurrence from the end back to the start and drops the call stack. You can even keep one rolling row if you want O(n) extra space.

Golang Solution

dp[i][j] is the cheapest path from (i, j) to the end. The helper is the Unique Paths shape: cache hit, else end cell, else down and right, then store. The combination is grid[i][j] + min(down, right) instead of down + right.

Time: O(m · n) — each cell is solved once
Space: O(m · n) — table, plus O(m + n) recursion depth

import "math"

func minPathSum(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
    }
    dp[0][0] = unique(m, n, 0, 0, grid, dp)
    return dp[0][0]
}

func unique(m, n, i, j int, grid, dp [][]int) int {
    if dp[i][j] > 0 {
        return dp[i][j]
    }

    if i == m-1 && j == n-1 {
        return grid[i][j]
    }

    down, right := math.MaxInt, math.MaxInt
    if i < m-1 {
        down = unique(m, n, i+1, j, grid, dp)
    }
    if j < n-1 {
        right = unique(m, n, i, j+1, grid, dp)
    }
    dp[i][j] = grid[i][j] + min(down, right)
    return dp[i][j]
}

A one-cell grid returns grid[0][0]. The memo test dp[i][j] > 0 matches Unique Paths; here a stored 0 looks uncached because the grid may contain zeros. The answer is still correct, it just recomputes those cells. A sentinel (fill dp with -1) closes that hole if you care.