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.

#64

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。示例 1：输入： grid = [[1,3,1],[1,5,1],[4,2,1]] 输出： 7 解释：因为路径 1→3→1→1→1 的总和…

数组动态规划矩阵

题目描述

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

提示：

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

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i][j]$ 表示从左上角走到 $(i, j)$ 位置的最小路径和。初始时 $f[0][0] = grid[0][0]$ ，答案为 $f[m - 1][n - 1]$ 。

考虑 $f[i][j]$ ：

如果 $j = 0$ ，那么 $f[i][j] = f[i - 1][j] + grid[i][j]$ ；
如果 $i = 0$ ，那么 $f[i][j] = f[i][j - 1] + grid[i][j]$ ；
如果 $i \gt 0$ 且 $j \gt 0$ ，那么 $f[i][j] = \min(f[i - 1][j], f[i][j - 1]) + grid[i][j]$ 。

最后返回 $f[m - 1][n - 1]$ 即可。

时间复杂度 $O(m \times n)$ ，空间复杂度 $O(m \times n)$ 。其中 $m$ 和 $n$ 分别是网格的行数和列数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#63 不同路径 II #85 最大矩形 #221 最大正方形