Problem #64: Minimum Path Sum

Intuition & Strategy Breakdown

Use dynamic programming. The minimum path sum to grid[i][j] is grid[i][j] + min(dp[i-1][j], dp[i][j-1]), using top/left boundary base cases.

Python Solution

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

Java Solution

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