带负值的最小路径和：动态规划（DP）是否仍适用？

原题描述 #

给定一个 m x n 的网格，网格里填充了非负整数，找到一条从左上角到右下角的路径，使得路径上所有数字的和最小。
注意：你只能在任何时间点向下或者向右移动。
示例：
输入：grid = [[1,3,1],
[1,5,1],
[4,2,1]]
输出：7
解释：路径 1 → 3 → 1 → 1 → 1 的和最小。

个人尝试与疑问 #

我尝试在网格中设置一些负值，发现如下动态规划转移公式似乎依然有效：
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

请问是否存在案例可以证明，当网格中存在负值时，该动态规划方法无法正确求解最小路径和？

结论与分析 #

结论 #

不存在这样的反例，该动态规划转移公式在网格包含负值时依然能正确求解最小路径和。

原因分析 #

因为题目限制了只能向右或向下移动，所以对于网格中的任意位置(i,j)，到达该位置的所有可能路径，只能来自两个方向：

• 从上方位置(i-1,j)向下移动一步
• 从左方位置(i,j-1)向右移动一步

因此，要得到(i,j)的最小路径和，必然是取这两个前驱位置的最小路径和中的较小值，再加上当前网格位置的数值grid[i][j]——不管这个数值是正还是负，这个逻辑都成立。

负值网格示例验证 #

比如以下包含负值的网格：

[[-1,  3,  2],
 [ 4, -5,  1],
 [ 2,  1, -3]]

按照公式计算得到的最终最小路径和为-5，手动枚举所有可能路径后可以确认，这确实是所有路径中的最小和，与公式计算结果一致。

内容的提问来源于stack exchange，提问作者noobie2023