How do you approach Minimum Path Sum?

Each cell's best cost is its value plus the cheaper of the cell above or to the left.

What are common mistakes on Minimum Path Sum?

Iterating the dimensions in an order that reads a cell before it has been written. Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input. Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.

Sitelet https://gitgood.dev/coding/minimum-path-sum

gitGood.dev

← Back to problems

Minimum Path Sum

MediumAlgorithms

Description

Given an m x n grid of non-negative numbers, find a path from the top-left to the bottom-right that minimizes the sum of the numbers along the path. You may only move right or down.

Return that minimum sum.

Example 1

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]

Output: 7

Explanation: Path 1 -> 3 -> 1 -> 1 -> 1 sums to 7.

Constraints

- m == grid.length - n == grid[i].length - 1 <= m, n <= 200 - 0 <= grid[i][j] <= 200

Minimum Path Sum: approach, complexity and pitfalls

A medium dynamic programming problem, graded against 7 test cases (5 of them hidden).

The pattern: Dynamic Programming

Overlapping subproblems solved once and reused - the pattern candidates fear most.

Reach for it when you see: "Number of ways", "minimum/maximum cost", or a recursion that recomputes the same state.

If you are stuck

Show the 2-step hint ladder

Each cell's best cost is its value plus the cheaper of the cell above or to the left.
Handle the first row and first column as edge cases.

The optimal approach

Show the approach: The approach

Grid DP. `dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])`, with the first row/column accumulating in a single direction. The bottom-right cell holds the answer.

Time: O(m·n). Space: O(m·n).

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Dynamic Programming mistakes

These apply to the pattern as a whole, not just this problem.

Iterating the dimensions in an order that reads a cell before it has been written.
Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input.
Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.