#64

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Minimum Path Sum

Compute the minimum sum from top-left to bottom-right in a grid using state transition dynamic programming efficiently.

Problem Statement

You are given an m x n grid filled with non-negative integers. The task is to determine a path from the top-left corner to the bottom-right corner that minimizes the sum of all numbers along the path. Movement is constrained to either moving right or down at each step, which limits available choices and guides the DP state transitions.

The problem provides an example grid: [[1,3,1],[1,5,1],[4,2,1]]. Following the allowed moves, the minimum path sum is 7 by taking the path 1 → 3 → 1 → 1 → 1. The goal is to compute such minimal sums efficiently, considering grids of up to 200x200 with values ranging from 0 to 200.

Examples

Example 1

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

Output: 7

Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

Example 2

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

Output: 12

Example details omitted.

Constraints

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

Solution Approach

Bottom-Up Dynamic Programming

Create a DP matrix of the same size as the input grid. Initialize the top-left cell with its original value. Iterate over each cell, updating its value to the minimum sum required to reach it from either the cell above or the cell to the left. Continue until reaching the bottom-right cell, which holds the final minimum path sum. This method directly uses the state transition property and ensures every cell reflects the optimal sum from the start.

Space Optimization

Instead of maintaining the full DP matrix, store only the current and previous rows, updating each cell in place. This reduces space complexity from O(m*n) to O(n), where n is the number of columns. You still compute each cell based on top and left values, preserving the correct DP state transitions. This approach is crucial for large grids and highlights the trade-off between space usage and code clarity while maintaining accurate minimum path calculations.

Edge Case Handling

Explicitly handle the first row and first column separately since they have only one possible previous cell to transition from. For the first row, only accumulate sums from the left; for the first column, accumulate sums from above. Correct handling of these edges avoids off-by-one errors in state transitions and ensures that the DP table is fully accurate. Neglecting this can produce wrong results, as the path sum depends heavily on correct initialization at borders.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(m n) because each cell is visited once and computed using its top and left neighbors. The space complexity can be O(m n) with full DP or O(n) with row optimization. These complexities reflect the state transition dynamic programming approach's efficiency in both time and memory usage for large grids.

What Interviewers Usually Probe

Do you understand how each cell's minimum sum depends on its top and left neighbors?
Can you optimize the space usage while maintaining correct DP transitions?
Will you correctly handle edge cases like the first row and first column for accurate sums?

Common Pitfalls or Variants

Common pitfalls

Failing to correctly initialize the first row or first column, leading to incorrect path sums.
Confusing the direction of allowed moves and attempting diagonal or upward transitions.
Using recursive solutions without memoization, causing time limit exceeded errors on large grids.

Follow-up variants

Minimum Path Sum II with obstacles blocking certain cells.
Maximum Path Sum on a grid with the same movement constraints.
Minimum Falling Path Sum allowing diagonal moves in addition to down and right.

FAQ

What is the key pattern used in Minimum Path Sum?

The problem uses state transition dynamic programming where each cell's minimal sum is determined from its top and left neighbors, forming a clear DP pattern.

How do I handle the first row and first column?

Initialize the first row by accumulating sums from the left and the first column from above. This ensures state transitions remain valid and avoids off-by-one errors.

Can this solution handle large grids efficiently?

Yes, with full DP the time complexity is O(m*n), and using a single-row optimization reduces space to O(n), making it feasible for grids up to 200x200.

What common mistakes occur with this problem?

Common pitfalls include ignoring edge initialization, attempting invalid moves like diagonals, or using plain recursion without memoization, which can cause incorrect results or TLE.

Are there follow-up variations I should consider?

Yes, variations include grids with obstacles, maximum path sum instead of minimum, and minimum falling path sums allowing diagonal moves, all requiring adapted DP transitions.

terminal

Solution

Solution 1: Dynamic Programming

We define $f[i][j]$ to represent the minimum path sum from the top left corner to $(i, j)$. Initially, $f[0][0] = grid[0][0]$, and the answer is $f[m - 1][n - 1]$.

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        f = [[0] * n for _ in range(m)]
        f[0][0] = grid[0][0]
        for i in range(1, m):
            f[i][0] = f[i - 1][0] + grid[i][0]
        for j in range(1, n):
            f[0][j] = f[0][j - 1] + grid[0][j]
        for i in range(1, m):
            for j in range(1, n):
                f[i][j] = min(f[i - 1][j], f[i][j - 1]) + grid[i][j]
        return f[-1][-1]

Continue Practicing

#63 unique paths ii #85 maximal rectangle #221 maximal square