Minimum Path Sum

Problem Description

Given a m x n grid filled with non-negative numbers, find a path from top-left to bottom-right, which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Examples

Constraints

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

State Transition and Space Optimization

Let dp[r][c] be the minimum path sum to reach cell (r, c). Since we can only move down or right, we must arrive at cell (r, c) from either the cell directly above (r - 1, c) or the cell directly left (r, c - 1). Thus: dp[r][c] = grid[r][c] + min(dp[r - 1][c], dp[r][c - 1])

We can optimize space to a 1D array dp of size cols:

• Initialize dp[0] = grid[0][0].
• For the first row, dp[c] = dp[c - 1] + grid[0][c].
• For subsequent rows:
  • dp[0] = dp[0] + grid[r][0] (can only come from above).
  • For c > 0, dp[c] = grid[r][c] + min(dp[c], dp[c - 1]).

Solution: 1D DP Array

class Solution {
    public int minPathSum(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        int[] dp = new int[cols];

        // Initialize first cell
        dp[0] = grid[0][0];

        // Initialize first row
        for (int c = 1; c < cols; c++) {
            dp[c] = dp[c - 1] + grid[0][c];
        }

        for (int r = 1; r < rows; r++) {
            dp[0] += grid[r][0]; // first column of current row
            for (int c = 1; c < cols; c++) {
                dp[c] = grid[r][c] + Math.min(dp[c], dp[c - 1]);
            }
        }

        return dp[cols - 1];
    }
}

class Solution:
    def minPathSum(self, grid: list[list[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        dp = [0] * cols

        dp[0] = grid[0][0]
        for c in range(1, cols):
            dp[c] = dp[c - 1] + grid[0][c]

        for r in range(1, rows):
            dp[0] += grid[r][0]
            for c in range(1, cols):
                dp[c] = grid[r][c] + min(dp[c], dp[c - 1])

        return dp[-1]

#include <vector>
#include <algorithm>

class Solution {
public:
    int minPathSum(std::vector<std::vector<int>>& grid) {
        int rows = grid.size();
        int cols = grid[0].size();
        std::vector<int> dp(cols);

        dp[0] = grid[0][0];
        for (int c = 1; c < cols; c++) {
            dp[c] = dp[c - 1] + grid[0][c];
        }

        for (int r = 1; r < rows; r++) {
            dp[0] += grid[r][0];
            for (int c = 1; c < cols; c++) {
                dp[c] = grid[r][c] + std::min(dp[c], dp[c - 1]);
            }
        }

        return dp[cols - 1];
    }
};

Complexity Analysis:

• Time Complexity: O(M * N) where M is rows and N is columns.
• Space Complexity: O(N) to store the 1D DP array.

← All Problems