京公网安备11010502063487号给定一个 m × n 的非负整数网格，从左上角走到右下角，每次只能向右或向下走一格，求路径上所有数字之和的最小值。和"不同路径"同一个网格结构，但这次每一步有代价，要的是最小值而不是路径数。动态规划：走到 (i, j) 的最小路径和，等于 (i, j) 自己的值，加上走到它上面和左边这两格的最小路径和里较小的那个；第一行只能从左边来，第一列只能从上面来。本文用真实数据展示"每一步走较小的邻居"这个直觉贪心为什么不对，验证动态规划与枚举全部路径的答案一致，给出五种语言的实现，并把填表做成分步演示。
完整题目见官方页面（链接在文末）。基准解是递归枚举所有路径取最小值（不做记忆化，只适合小网格）。一共 12 组用例，覆盖：官方示例、单个格子、单行、单列、全是 0、绕过一个很大的数的情形：
输入 [[[1,3,1],[1,5,1],[4,2,1]]] 输出 7 输入 [[[1,2,3],[4,5,6]]] 输出 12 输入 [[[5]]] 输出 5 输入 [[[1,2,3]]] 输出 6 输入 [[[1],[2],[3]]] 输出 6 输入 [[[0,0],[0,0]]] 输出 0
一个自然的想法：站在某个格子，看看右边和下边哪个数更小，就走过去。但走到一个小数之后，后面可能被迫经过更大的数。下面是这种贪心写法与 solve 的真实结果：
# 每一步都走较小邻居的贪心写法 [[1, 2, 3], [4, 5, 6]]: 贪心 -> 12 solve -> 12 [[1, 2, 5], [3, 2, 1]]: 贪心 -> 6 solve -> 6 [[1, 3, 1], [1, 5, 1], [4, 2, 1]]: 贪心 -> 9 solve -> 7 [[1, 2], [1, 1]]: 贪心 -> 3 solve -> 3 [[1, 100, 1], [2, 1, 1]]: 贪心 -> 5 solve -> 5 随机 20000 个网格：贪心与最优解不同的有 4991 个（25.0%）
官方示例 [[1, 3, 1], [1, 5, 1], [4, 2, 1]]：贪心从 1 出发，右边是 3、下边是 1，走下面的 1，然后右边 5、下边 4，走 4，之后 2、1，总和是 1 + 1 + 4 + 2 + 1 = 9；而最优路径是向右走 3、1，再向下走 1、1，总和是 7。前两组和第四、五组贪心碰巧和最优一致。在随机生成的 20000 个网格上，贪心写法与最优解不同的有 4991 个，占 25.0%。
dp[j] 是走到当前行第 j 列的最小路径和。对每个格子：起点是它自己；第一行只能从左边来：dp[j] = dp[j-1] + grid[i][j]；第一列只能从上面来：dp[j] 保持上一行的值再加上自己；其他格子取 min(dp[j], dp[j-1])（前者是从上面来，后者是从左边来）再加上自己。返回 dp[n-1]。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。
Python · 解法代码def solve(grid): m, n = len(grid), len(grid[0]) dp = [0] * n # dp[j]：走到当前行第 j 列的最小路径和 for i in range(m): for j in range(n): if i == 0 and j == 0: dp[j] = grid[0][0] elif i == 0: dp[j] = dp[j - 1] + grid[i][j] # 第一行：只能从左边来 elif j == 0: dp[j] = dp[j] + grid[i][j] # 第一列：只能从上面来（dp[j] 还是上一行的值） else: dp[j] = min(dp[j], dp[j - 1]) + grid[i][j] # 从上面或左边来，取较小的 return dp[n - 1]
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [[[1,3,1],[1,5,1],[4,2,1]]] → 7 [[[1,2,3],[4,5,6]]] → 12 [[[5]]] → 5 [[[1,2,3]]] → 6 [[[1],[2],[3]]] → 6 [[[0,0],[0,0]]] → 0
Java · 解法代码class Solution { public int minPathSum(int[][] grid) { int m = grid.length, n = grid[0].length; int[] dp = new int[n]; // dp[j]：走到当前行第 j 列的最小路径和 for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (i == 0 && j == 0) dp[j] = grid[0][0]; else if (i == 0) dp[j] = dp[j - 1] + grid[i][j]; // 第一行：只能从左边来 else if (j == 0) dp[j] = dp[j] + grid[i][j]; // 第一列：只能从上面来（dp[j] 还是上一行的值） else dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j]; // 从上面或左边来，取较小的 } } return dp[n - 1]; } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [[[1,3,1],[1,5,1],[4,2,1]]] → 7 [[[1,2,3],[4,5,6]]] → 12 [[[5]]] → 5 [[[1,2,3]]] → 6 [[[1],[2],[3]]] → 6 [[[0,0],[0,0]]] → 0
Go · 解法代码func minPathSum(grid [][]int) int { m, n := len(grid), len(grid[0]) dp := make([]int, n) // dp[j]：走到当前行第 j 列的最小路径和 for i := 0; i < m; i++ { for j := 0; j < n; j++ { switch { case i == 0 && j == 0: dp[j] = grid[0][0] case i == 0: // 第一行：只能从左边来 dp[j] = dp[j-1] + grid[i][j] case j == 0: // 第一列：只能从上面来（dp[j] 还是上一行的值） dp[j] += grid[i][j] default: // 从上面或左边来，取较小的 if dp[j-1] < dp[j] { dp[j] = dp[j-1] } dp[j] += grid[i][j] } } } return dp[n-1] }
$ go build -o bin . && ./bin < cases.jsonl [[[1,3,1],[1,5,1],[4,2,1]]] → 7 [[[1,2,3],[4,5,6]]] → 12 [[[5]]] → 5 [[[1,2,3]]] → 6 [[[1],[2],[3]]] → 6 [[[0,0],[0,0]]] → 0
JavaScript · 解法代码function minPathSum(grid) { const m = grid.length, n = grid[0].length; const dp = new Array(n).fill(0); // dp[j]：走到当前行第 j 列的最小路径和 for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { if (i === 0 && j === 0) dp[j] = grid[0][0]; else if (i === 0) dp[j] = dp[j - 1] + grid[i][j]; // 第一行：只能从左边来 else if (j === 0) dp[j] = dp[j] + grid[i][j]; // 第一列：只能从上面来（dp[j] 还是上一行的值） else dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j]; // 从上面或左边来，取较小的 } } return dp[n - 1]; }
$ node run.js < cases.jsonl [[[1,3,1],[1,5,1],[4,2,1]]] → 7 [[[1,2,3],[4,5,6]]] → 12 [[[5]]] → 5 [[[1,2,3]]] → 6 [[[1],[2],[3]]] → 6 [[[0,0],[0,0]]] → 0
C++ · 解法代码#include <algorithm> #include <vector> using namespace std; class Solution { public: int minPathSum(vector<vector<int>>& grid) { int m = grid.size(), n = grid[0].size(); vector<int> dp(n, 0); // dp[j]：走到当前行第 j 列的最小路径和 for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (i == 0 && j == 0) dp[j] = grid[0][0]; else if (i == 0) dp[j] = dp[j - 1] + grid[i][j]; // 第一行：只能从左边来 else if (j == 0) dp[j] = dp[j] + grid[i][j]; // 第一列：只能从上面来（dp[j] 还是上一行的值） else dp[j] = min(dp[j], dp[j - 1]) + grid[i][j]; // 从上面或左边来，取较小的 } } return dp[n - 1]; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [[[1,3,1],[1,5,1],[4,2,1]]] → 7 [[[1,2,3],[4,5,6]]] → 12 [[[5]]] → 5 [[[1,2,3]]] → 6 [[[1],[2],[3]]] → 6 [[[0,0],[0,0]]] → 0
共 12 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 12/12 Java 通过 12/12 Go 通过 12/12 JavaScript 通过 12/12 C++ 通过 12/12
网格边长 m = n 分别为 6、8、10、12，格子里是 0 到 9 的整数，每个规模取三次中最快的一次：
m = n | 暴力解 | 本文解法
6 | 0.120 ms | 0.002 ms
8 | 1.749 ms | 0.004 ms
10 | 24.729 ms | 0.006 ms
12 | 358.840 ms | 0.009 ms递归枚举（基准）随网格边长每增加 2，耗时增加约 14 倍到 15 倍（0.120ms、1.749ms、24.729ms、358.840ms），是指数增长；动态规划的耗时只有 0.002 毫秒到 0.009 毫秒，随格子数（n²）缓慢增长。n = 12 时，枚举用了 358.8ms，动态规划 0.009ms。
Python 版本另外和递归枚举做了随机对拍：行数、列数各取 1 到 6，格子取 0 到 9 的随机整数：
随机对拍 20000 组（行数、列数各取 1 到 6，格子取 0 到 9 的随机整数），solve 与 brute 的结果全部一致。
另外四种语言只在上面 12 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用官方示例 [[1, 3, 1], [1, 5, 1], [4, 2, 1]]。第一行依次是 1、4、5（只能从左边来）；第一列依次是 1、2、6（只能从上面来）；其余格子取 min(上面, 左边) 加上自己，例如 (1, 1) 是 min(4, 2) + 5 = 7。最后右下角是 7。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。