Minimum Path Sum

MEDIUM✓ CHIP-TIMEDLC #64 — FULL STATEMENT ↗

The drill: Same right/down grid walk again, but every cell now costs something to enter. Find the cheapest possible route from the top-left corner to the bottom-right corner.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

Once again a grid walk from the top-left corner to the bottom-right corner using only right and down moves, but this time every cell carries a cost to enter, including the starting cell.

The task is to find the cheapest possible total cost across every valid route — summing the cost of every cell the route actually steps on, including both corners.

There's no way to skip a cell's cost partway through a route; every cell visited contributes its full value to the running total.

EX 01

grid = [[5]]

→ 5

SINGLE CELL

EX 02

grid = [[1, 2, 3]]

→ 6

SINGLE ROW, ONLY ONE ROUTE EXISTS

EX 03

grid = [[1], [2], [3]]

→ 6

SINGLE COLUMN, ONLY ONE ROUTE EXISTS

grid values are non-negative costs
movement is limited to a single step right or a single step down
the starting cell's cost counts toward the total too
grid sizes stay small enough for an O(m·n) table

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Cost only comes from the cells a route actually enters, and every route starts and ends at the same two corners. What's the cheapest way to arrive at any single cell along the way?

HINT 2 THE STRUCTURE

The cheapest way into a cell is whichever is cheaper — arriving from above or arriving from the left — plus that cell's own cost. Nothing else about the rest of the grid matters yet.

HINT 3 ONE STEP FROM THE ANSWER

DP: cost[r][c] = grid[r][c] + min(cost[r-1][c], cost[r][c-1]), with the first row and column filled as running sums since they only have one way in. The bottom-right cell holds the answer.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE CHEAPEST ENTRYPATTERN · GRID DP, CHEAPEST ENTRYgrid = [[3,1,2],[2,5,1],[4,2,1]]

STEP 1

Seed the top-left with its own cost, 3 — the only way to start.

STEP 1 / 5 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/minimum-path-sum.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        row = [0] * n
        row[0] = grid[0][0]
        for c in range(1, n):
            row[c] = row[c - 1] + grid[0][c]
        for r in range(1, m):
            row[0] += grid[r][0]
            for c in range(1, n):
                row[c] = grid[r][c] + min(row[c], row[c - 1])
        return row[-1]

TIME O(M·N)SPACE O(N)PYTHON · RACE PACE · 12 LN

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])

        def cost(r, c):
            if r == m - 1 and c == n - 1:
                return grid[r][c]
            if r == m - 1:
                return grid[r][c] + cost(r, c + 1)
            if c == n - 1:
                return grid[r][c] + cost(r + 1, c)
            return grid[r][c] + min(cost(r + 1, c), cost(r, c + 1))

        return cost(0, 0)

TIME O(2^(M+N))SPACE O(M+N)PYTHON · TRAINING PACE · 14 LN

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[] row = new int[n];
        row[0] = grid[0][0];
        for (int c = 1; c < n; c++) {
            row[c] = row[c - 1] + grid[0][c];
        }
        for (int r = 1; r < m; r++) {
            row[0] += grid[r][0];
            for (int c = 1; c < n; c++) {
                row[c] = grid[r][c] + Math.min(row[c], row[c - 1]);
            }
        }
        return row[n - 1];
    }
}

TIME O(M·N)SPACE O(N)JAVA · RACE PACE · 17 LN

class Solution {
    private int[][] grid;
    private int m, n;

    public int minPathSum(int[][] grid) {
        this.grid = grid;
        m = grid.length;
        n = grid[0].length;
        return cost(0, 0);
    }

    private int cost(int r, int c) {
        if (r == m - 1 && c == n - 1) {
            return grid[r][c];
        }
        if (r == m - 1) {
            return grid[r][c] + cost(r, c + 1);
        }
        if (c == n - 1) {
            return grid[r][c] + cost(r + 1, c);
        }
        return grid[r][c] + Math.min(cost(r + 1, c), cost(r, c + 1));
    }
}

TIME O(2^(M+N))SPACE O(M+N)JAVA · TRAINING PACE · 24 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED