⚡Flashcard Drill➔
NeetCode #714LC-64Medium2-D Dynamic ProgrammingNC 250
← Back to All Problems

#714 · #64 · Minimum Path Sum(最小路径和)

📌 Problem Statement & Constraints

Given an m x n grid of non-negative integers, find a path from the top-left to the bottom-right (moving right or down) that minimises the sum of the numbers along the path. Constraints: 1 <= m, n <= 200, 0 <= grid[i][j] <= 200.

💡 Core Algorithmic Approaches

  1. dp[i][j] is the minimum sum to reach (i, j).
  2. dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]).
  3. The first row and column accumulate their values, since only one route reaches them.
  4. A rolling row keeps the space at O(n).

💻 Benchmark Python3 Implementation

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

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m * n): every cell is visited once.
💾 Space Complexity
O(n): a single row.

⚠️ Interview Pitfalls & Follow-ups

  • Initialising the whole table to 0: the first row and column must accumulate, not start from zero.
  • Using max instead of min: this is a minimisation.
  • Skipping the first row and column setup: the interior recurrence needs valid boundary values.
  • Assuming non-negative values permit a greedy walk: the min-sum path still requires the full DP.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related 2-D Dynamic Programming Problems