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
dp[i][j]is the minimum sum to reach(i, j).dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]).- The first row and column accumulate their values, since only one route reaches them.
- 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
maxinstead ofmin: 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.