LeetCode-Go 中 64. Minimum Path Sum 的两种动态规划解法从 O(n²) 二维 DP 到原地零空间优化【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本文基于 LeetCode-Go 仓库中第 64 题「Minimum Path Sum最小路径和」的题解文档与配套源码完整讲解这道经典网格动态规划题的建模方式如何推导出状态转移方程dp[i][j] grid[i][j] min(dp[i-1][j], dp[i][j-1])如何从标准二维 DP 逐步优化到直接在原数组上原地 DP、使额外空间复杂度降为 0并结合仓库中的真实实现与测试用例说明空网格等边界条件的处理方式。题目描述与输入输出约定LeetCode 第 64 题的原始描述如下见 题解文档Given amxngrid filled with non-negative numbers, find a path from top left to bottom right whichminimizesthe sum of all numbers along its path.Note: You can only move either down or right at any point in time.即给定一个填充了非负整数的 m × n 网格找出从左上角到右下角的一条路径使得路径上经过的数字总和最小任何时刻只能向下或向右移动一步。示例Input: [ [1,3,1], [1,5,1], [4,2,1] ] Output: 7 Explanation: Because the path 1→3→1→1→1 minimizes the sum.题目大意仓库内 中文 README 的表述给定一个包含非负整数的 m × n 网格找出一条从左上角到右下角的路径使路径上的数字总和最小。每次只能向下或向右移动一步。由于只能向右或向下移动任意一条从(0,0)到(m-1,n-1)的路径恰好包含 mn-2 步m-1 次向下、n-1 次向右且路径中每个格子的访问顺序被其坐标唯一确定——这正是该题可以用动态规划高效求解的根本原因到达每个格子的最优路径只可能来自它的上方或左方。解题思路与状态转移方程文档给出的解题思路是在网格上求出从左上角到右下角、数字之和最小的路径输出这个和。最直白的想法是用一个二维数组做 DP最原始的做法。由于只能往下和往右走只需维护相邻两列的信息从左往右逐列推进即可得到最优解进一步地可以直接在原始数组上做原地 DP额外空间复杂度为 0。设dp[i][j]表示从左上角(0,0)走到格子(i,j)的最小路径和则状态转移方程为dp[i][j] grid[i][j] min(dp[i-1][j], dp[i][j-1])边界初始化dp[0][0] grid[0][0] dp[i][0] grid[i][0] dp[i-1][0] // 第一列只能从上方到达 dp[0][j] grid[0][j] dp[0][j-1] // 第一行只能从左方到达最终答案即dp[m-1][n-1]。以示例网格手工推演一遍原始 grid DP 后的最小路径和 1 3 1 1 4 5 1 5 1 2 9 6 4 2 1 6 8 7右下角的 7 对应路径 1→3→1→1→1与题目示例输出一致。该算法的时间复杂度为 O(m·n)每个格子恰好被访问并计算一次空间复杂度取决于实现方式下面给出仓库中的两种实现。解法一二维 DP 表辅助空间 O(m·n)这是文档所称「最原始的方法」对应仓库源码 64. Minimum Path Sum.go 中的minPathSum1函数// 解法二 最原始的方法辅助空间 O(n^2) func minPathSum1(grid [][]int) int { if len(grid) 0 { return 0 } m, n : len(grid), len(grid[0]) if m 0 || n 0 { return 0 } dp : make([][]int, m) for i : 0; i m; i { dp[i] make([]int, n) } // initFirstCol for i : 0; i len(dp); i { if i 0 { dp[i][0] grid[i][0] } else { dp[i][0] grid[i][0] dp[i-1][0] } } // initFirstRow for i : 0; i len(dp[0]); i { if i 0 { dp[0][i] grid[0][i] } else { dp[0][i] grid[0][i] dp[0][i-1] } } for i : 1; i m; i { for j : 1; j n; j { dp[i][j] min(dp[i-1][j], dp[i][j-1]) grid[i][j] } } return dp[m-1][n-1] }实现要点防御性判空函数开头对len(grid) 0与m 0 || n 0两种空输入情形直接返回 0保证[][]int{}空切片与[][]int{{}}含一个空行的切片都能安全处理分配 dp 表用make([][]int, m)加逐行make([]int, n)构造 m × n 的二维表Go 中二维切片需要这样逐行初始化初始化首列 / 首行两段独立循环分别累加第一列与第一行的前缀和对应上文边界公式主转移双重循环从dp[1][1]开始按grid[i][j] min(dp[i-1][j], dp[i][j-1])填充剩余格子返回答案dp[m-1][n-1]即为最小路径和。其中min是 同一文件底部的辅助函数func min(a int, b int) int { if a b { return b } return a }解法二原地 DP额外空间 O(1)文档指出的优化方向是既然dp[i][j]只依赖已经算过的上方格子和左方格子那么完全可以不新开 dp 表直接把 grid 本身当作 dp 表。当按「先逐行、再逐列」的顺序扫描时grid[i-1][j]上方与grid[i][j-1]左方在被读取时恰好已被更新为路径和原始权重值不再需要保留——这就是所谓空间复杂度为 0 的写法。对应仓库源码 minPathSum 函数// 解法一 原地 DP无辅助空间 func minPathSum(grid [][]int) int { m, n : len(grid), len(grid[0]) for i : 1; i m; i { grid[i][0] grid[i-1][0] } for j : 1; j n; j { grid[0][j] grid[0][j-1] } for i : 1; i m; i { for j : 1; j n; j { grid[i][j] min(grid[i-1][j], grid[i][j-1]) } } return grid[m-1][n-1] }与解法一逐段对照步骤解法一dp 表解法二原地首列初始化dp[i][0] grid[i][0] dp[i-1][0]grid[i][0] grid[i-1][0]首行初始化dp[0][j] grid[0][j] dp[0][j-1]grid[0][j] grid[0][j-1]主转移dp[i][j] min(dp[i-1][j], dp[i][j-1]) grid[i][j]grid[i][j] min(grid[i-1][j], grid[i][j-1])返回值dp[m-1][n-1]grid[m-1][n-1]可以注意两个细节原地写法省去了空输入判空。len(grid[0])在grid为空切片时会直接 panic因此该解法只对非空网格有效——这一点在测试文件中有明确体现后文说明原地 DP 有一个隐含前提调用方不再需要保留原始 grid。本例中 grid 只是输入参数、用完即弃所以原地改写是安全的如果调用方还要复用原网格就必须回到解法一或滚动数组写法。文档思路中提到的「只需维护 2 列信息从左边推到最右边」是滚动数组思路只保留当前列与上一列两个一维切片把空间进一步压到 O(min(m, n))。原地 DP 则比滚动数组更激进直接压缩到 O(1) 额外空间是本题空间维度的最优解。测试用例与边界条件验证仓库为该题配套的测试文件是 64. Minimum Path Sum_test.go它覆盖了三类输入并展示了两个解法的边界差异qs : []question64{ { para64{[][]int{ {1, 3, 1}, {1, 5, 1}, {4, 2, 1}, }}, ans64{7}, }, { para64{[][]int{}}, ans64{0}, }, { para64{[][]int{{}}}, ans64{0}, }, }标准样例3×3 网格期望输出 7与题面示例一致空切片[][]int{}两个解法都应返回 0。解法二minPathSum1靠开头的判空分支覆盖含空行的切片[][]int{{}}同样期望 0。测试注释写明minPathSum1 covers the empty/zero-size guard branches即解法一负责覆盖这些防御分支。测试循环中有一段值得注意的逻辑测试文件第 60–77 行// minPathSum1 covers the empty/zero-size guard branches got1 : minPathSum1(cloneGrid64(p.og)) ... // minPathSum panics on empty grid, so only call it on non-empty input if len(p.og) 0 len(p.og[0]) 0 { got : minPathSum(cloneGrid64(p.og)) ... }注释明确指出原地解法minPathSum在空网格上会 panic因此测试只对非空输入调用它空输入全部交给带判空的minPathSum1。这正是上一节提到的「原地写法省略了判空」在测试层面的印证——两种解法在仓库中是分工配合的解法二演示 O(1) 空间的最优形态解法一兜底空输入场景。另外测试还提供了一个细节工具函数cloneGrid64用于在调用解法前深拷贝输入网格func cloneGrid64(g [][]int) [][]int { c : make([][]int, len(g)) for i : range g { c[i] make([]int, len(g[i])) copy(c[i], g[i]) } return c }这个克隆并非可有可无因为minPathSum会原地改写grid若不先克隆同一份输入先经过minPathSum再传给其他断言或打印时就已经被污染。这也从侧面说明了原地 DP 的副作用——它把「读入参」变成了「写入参」。在本地运行测试仓库提供了一键覆盖率脚本 gotest.shgo test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...该命令对leetcode/目录下所有包含本题一次性生成合法的单一覆盖率文件coverage.txt脚本注释解释了为何不使用旧式「逐包 -coverprofile 再 cat 追加」的写法——后者会产出重复的mode: atomic头被新版 Codecov 上传器判为 0% 覆盖率。若只想单独运行第 64 题的测试可执行go test -v ./leetcode/0064.Minimum-Path-Sum/预期输出中包含【input】与【output】的对照打印例如标准样例对应【output】:7。注意模块声明见 go.modGo 版本基线为 1.19。两种解法小结维度minPathSum1二维 DP 表minPathSum原地 DP时间复杂度O(m·n)O(m·n)额外空间O(m·n)O(1)空输入[][]int{}/[][]int{{}}安全返回 0会 panic需调用方保证非空是否改写输入 grid否是grid 被覆写为路径和表适用场景需要保留原始网格、或需统一处理空输入输入可被消费、追求最小空间开销本题的完整材料在仓库中的位置题解文档英文website/content.en/ChapterFour/0001~0099/0064.Minimum-Path-Sum.mdGo 题解源码leetcode/0064.Minimum-Path-Sum/64. Minimum Path Sum.go单元测试leetcode/0064.Minimum-Path-Sum/64. Minimum Path Sum_test.go中文 READMEleetcode/0064.Minimum-Path-Sum/README.md覆盖率测试脚本gotest.sh掌握本题后可以得到一条通用的网格 DP 优化路径先写清晰的二维 DP 表 → 观察转移只依赖上一行/列 → 滚动数组 → 原地改写。Minimum Path Sum 因为每个格子只依赖「上、左」两个已算状态是原地化改造最容易成功的一类题也是理解 LeetCode-Go 仓库中其他网格 DP 题解如同章节的最小路径类问题的一个典型样本。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考