Problem statement

Given an m × n grid of non-negative numbers, find a path from the top-left corner to the bottom-right corner that minimises the sum of the numbers along it.

You may only move down or right at each step. Return that minimum sum.

Example 1

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: The path 1 → 3 → 1 → 1 → 1 sums to 7.

Example 2

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

Example 3

Input: grid = [[5]]
Output: 5

Constraints

• 1 <= grid.length, grid[i].length <= 8
• 0 <= grid[i][j] <= 200

Hints for Minimum Path Sum

1. Hint 1

   A cell is reachable only from above or from the left, so its best cost is its own value plus the cheaper of those two.

2. Hint 2

   The first row and first column have exactly one way in — fill them as running sums first.

3. Hint 3

   You can overwrite the grid in place, since every cell is read only by cells below and to the right.

How to solve Minimum Path Sum

A cell is entered from above or from the left, so its best cost is its value plus the cheaper of those two predecessors.

Approach

1. Fill the first row and first column as running sums — each has one way in.
2. For every other cell, dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1]).
3. Return dp[m-1][n-1].

Why it works

With only down and right moves, every path to (r, c) passes through exactly one of (r-1, c) or (r, c-1) last, so the optimal cost decomposes over that choice. Row-major order ensures both predecessors are ready.

Complexity

• Time — O(m · n)
• Space — O(m · n), or O(1) extra by overwriting the grid

Pitfalls

• Greedy (always take the smaller neighbour) is wrong — a cheap step can lead into an expensive corridor.

Reference solution

Python

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

Java

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

C++

int minPathSum(vector<vector<int>>& grid) {
    int m = (int) grid.size(), n = (int) grid[0].size();
    vector<vector<int>> dp = grid;
    for (int c = 1; c < n; c++) dp[0][c] += dp[0][c - 1];
    for (int r = 1; r < m; r++) dp[r][0] += dp[r - 1][0];
    for (int r = 1; r < m; r++) {
        for (int c = 1; c < n; c++) {
            dp[r][c] += min(dp[r - 1][c], dp[r][c - 1]);
        }
    }
    return dp[m - 1][n - 1];
}

JavaScript

var minPathSum = function(grid) {
    const m = grid.length, n = grid[0].length;
    const dp = [];
    for (let r = 0; r < m; r++) dp.push(grid[r].slice());
    for (let c = 1; c < n; c++) dp[0][c] += dp[0][c - 1];
    for (let r = 1; r < m; r++) dp[r][0] += dp[r - 1][0];
    for (let r = 1; r < m; r++) {
        for (let c = 1; c < n; c++) {
            dp[r][c] += Math.min(dp[r - 1][c], dp[r][c - 1]);
        }
    }
    return dp[m - 1][n - 1];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium