Minimum Path Sum

Problem

Given an m × n grid of non-negative integers, find a path from top-left to bottom-right that minimizes the sum of values along it. You can only move right or down.

Constraints

• 1 ≤ m,n ≤ 200
• 0 ≤ grid[i][j] ≤ 200

Approach — Dynamic Programming

This is a Dynamic Programming problem. The idea: break the problem into overlapping subproblems and build the answer up, caching results so nothing is recomputed. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) to O(n²) time.

Solution code

Python

class Solution:
    def minPathSum(self, grid):
        rows, cols = len(grid), len(grid[0])
        dp = [0] * cols
        for r in range(rows):
            for c in range(cols):
                if r == 0 and c == 0:
                    dp[c] = grid[r][c]
                elif r == 0:
                    dp[c] = dp[c - 1] + grid[r][c]
                elif c == 0:
                    dp[c] = dp[c] + grid[r][c]
                else:
                    dp[c] = min(dp[c], dp[c - 1]) + grid[r][c]
        return dp[-1]

Java

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

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.