示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载本篇技术指南以 doocs/leetcode 仓库中 lcof2/剑指 Offer II 099. 最小路径之和/README.md 为核心系统拆解这道经典的二维动态规划题如何从路径数量指数爆炸的暴力搜索收敛到每个格子只算一次的填表法并给出仓库内 Python、Java、C、Go、TypeScript、C#、Swift 等全套可运行实现。读完你不仅能独立写出 O(m×n) 的标准解法还能理解如何通过原地复用网格把空间复杂度压到 O(1)。一、题目概述与约束条件给定一个包含非负整数的m × 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] 100格子值为非负整数说明本题与主站 64. 最小路径和 为同一道题解法完全通用主站版本中单个格子取值上限为 200差异不影响算法设计。二、为什么暴力搜索不可行在网格中只能向右或向下移动从左上角走到右下角恰好要走(m - 1) (n - 1)步其中选择m - 1步向下即可确定整条路径因此路径总条数为组合数C(m n - 2, m - 1)当m, n 200时路径条数随格子数指数增长。若枚举全部路径再取数字和最小者必然无法在时限内完成。同时同一条路径会被多条不同走法反复经过子问题大量重叠——这正是动态规划发挥作用的典型特征。三、动态规划解法状态设计与转移方程状态定义用dp[i][j]主站版本中记为f[i][j]二者是同一概念表示从左上角(0, 0)走到(i, j)位置的最小路径和。由于机器人只能向下或向右移动到达(i, j)的前一步只可能来自上方(i-1, j)或左方(i, j-1)因此其最优值只取决于这两个方向的较小者再加上当前格子自身的值。边界与递推关系起点dp[0][0] grid[0][0]答案为dp[m-1][n-1]第一列j 0只能从上方唯一方向累加dp[i][0] dp[i-1][0] grid[i][0]第一行i 0只能从左侧唯一方向累加dp[0][j] dp[0][j-1] grid[0][j]内部格子i 0且j 0dp[i][j] min(dp[i-1][j], dp[i][j-1]) grid[i][j]算法流程初始化dp二维数组并将dp[0][0]置为grid[0][0]按行方向预处理第一列的累加和按列方向预处理第一行的累加和双重循环遍历内部格子套用上述递推公式返回dp[m-1][n-1]。复杂度时间复杂度O(m × n)每个格子只被计算一次空间复杂度O(m × n)需要一张与网格同尺寸的 DP 表。其中m、n分别为网格行数与列数。四、多语言实现以下实现均完整取自仓库对应目录可直接提交运行。Python3class Solution: def minPathSum(self, grid: List[List[int]]) - int: m, n len(grid), len(grid[0]) dp [[grid[0][0]] * n for _ in range(m)] for i in range(1, m): dp[i][0] dp[i - 1][0] grid[i][0] for j in range(1, n): dp[0][j] dp[0][j - 1] grid[0][j] for i in range(1, m): for j in range(1, n): dp[i][j] min(dp[i - 1][j], dp[i][j - 1]) grid[i][j] return dp[-1][-1]Javaclass Solution { public int minPathSum(int[][] grid) { int m grid.length, n grid[0].length; int[][] dp new int[m][n]; dp[0][0] grid[0][0]; for (int i 1; i m; i) { dp[i][0] dp[i - 1][0] grid[i][0]; } for (int j 1; j n; j) { dp[0][j] dp[0][j - 1] grid[0][j]; } for (int i 1; i m; i) { for (int j 1; j n; j) { dp[i][j] Math.min(dp[i - 1][j], dp[i][j - 1]) grid[i][j]; } } return dp[m - 1][n - 1]; } }Cclass Solution { public: int minPathSum(vectorvectorint grid) { int m grid.size(), n grid[0].size(); vectorvectorint dp(m, vectorint(n, grid[0][0])); for (int i 1; i m; i) { dp[i][0] dp[i - 1][0] grid[i][0]; } for (int j 1; j n; j) { dp[0][j] dp[0][j - 1] grid[0][j]; } for (int i 1; i m; i) { for (int 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]; } };Gofunc minPathSum(grid [][]int) int { m, n : len(grid), len(grid[0]) dp : make([][]int, m) for i : 0; i m; i { dp[i] make([]int, n) } dp[0][0] grid[0][0] for i : 1; i m; i { dp[i][0] dp[i-1][0] grid[i][0] } for j : 1; j n; j { dp[0][j] dp[0][j-1] grid[0][j] } 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] }TypeScriptfunction minPathSum(grid: number[][]): number { let m grid.length, n grid[0].length; let dp Array.from({ length: m }, v new Array(n).fill(0)); dp[0][0] grid[0][0]; for (let i 1; i m; i) { dp[i][0] dp[i - 1][0] grid[i][0]; } for (let j 1; j n; j) { dp[0][j] dp[0][j - 1] grid[0][j]; } // dp for (let i 1; i m; i) { for (let j 1; j n; j) { let cur grid[i][j]; dp[i][j] cur Math.min(dp[i - 1][j], dp[i][j - 1]); } } return dp[m - 1][n - 1]; }C#public class Solution { public int MinPathSum(int[][] grid) { int m grid.Length, n grid[0].Length; int[,] dp new int[m, n]; dp[0, 0] grid[0][0]; for (int i 1; i m; i) { dp[i, 0] dp[i - 1, 0] grid[i][0]; } for (int j 1; j n; j) { dp[0, j] dp[0, j - 1] grid[0][j]; } for (int i 1; i m; i) { for (int j 1; j n; j) { dp[i, j] Math.Min(dp[i - 1, j], dp[i, j - 1]) grid[i][j]; } } return dp[m- 1, n - 1]; } }Swiftclass Solution { func minPathSum(_ grid: [[Int]]) - Int { let m grid.count let n grid[0].count var dp grid for i in 1..m { dp[i][0] dp[i-1][0] } for j in 1..n { dp[0][j] dp[0][j-1] } for i in 1..m { for j in 1..n { dp[i][j] min(dp[i-1][j], dp[i][j-1]) } } return dp[m-1][n-1] } }上述全部代码分别对应仓库中的 Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.cs、Solution.swift。五、空间优化从 O(m×n) 到 O(1)标准写法需要一张与网格同尺寸的 DP 表。由于递推dp[i][j]只依赖当前行左侧与上一行同列两个值可以复用原网格原地累加空间复杂度降为O(1)。这一优化思路在仓库源码中已有直接体现主站 64 题目录下的 Solution.swift 与 Solution.rs 均采用原地修改——Swift 版本将grid直接作为dp使用var dp gridRust 版本则声明mut grid后直接累加impl Solution { pub fn min_path_sum(mut grid: VecVeci32) - i32 { let m grid.len(); let n grid[0].len(); for i in 1..m { grid[i][0] grid[i - 1][0]; } for i in 1..n { grid[0][i] grid[0][i - 1]; } for i in 1..m { for j in 1..n { grid[i][j] grid[i][j - 1].min(grid[i - 1][j]); } } grid[m - 1][n - 1] } }两种写法时间复杂度均为O(m × n)区别仅在是否额外开辟 DP 表原地累加不改变正确性因为每个格子只被读取一次用于更新自身覆盖顺序与拓扑序一致。仓库中 0064.Minimum Path Sum 的 README 还提供了 JavaScript 等其他语言版本可供对照阅读。六、总结与延伸这道题是网格类二维 DP的标准入门模型核心套路可以提炼为三步定义dp[i][j]为到达该格子的最优值 → 根据移动规则确定前驱状态上方、左方→ 按拓扑序填表。在 lcof2/README.md 中与本题同属「数组 / 动态规划 / 矩阵」标签的还有一系列递进题目可以按序练习剑指 Offer II 098「路径的数目」同样是走网格但求的是路径条数对应计数型 DP剑指 Offer II 100「三角形中最小路径之和」把矩形网格换成三角形考察状态定义随图形结构的变化剑指 Offer II 107「矩阵中的距离」从最短路径视角扩展到 BFS / DP 混合场景。掌握最小路径之和这道题后你对最优子结构 重叠子问题的理解会自然迁移到上述兄弟题目中刷题效率将显著提升。赞分享示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐material-components-web Select 组件完整指南MDC Select 下拉菜单的安装、结构、样式与 API 详解material components web Select 组件完整指南MDC Select 下拉菜单的安装、结构、样式与 API 详解 本篇指南以 pac前端UI组件设计系统剑指 Offer II 091. 粉刷房子动态规划最小刷漆成本的多语言实现解析剑指 Offer II 091. 粉刷房子动态规划最小刷漆成本的多语言实现解析 导读 《剑指 Offer II 091. 粉刷房子》与 LeetCode 主示例工程下降路径最小和LeetCode 931动态规划题解状态转移、边界处理与空间优化下降路径最小和LeetCode 931动态规划题解状态转移、边界处理与空间优化 导读 本文基于「算法通关手册」仓库中的 0931. 下降路径最小和题解 h教程教育上一篇NanoClaw 安装接线Setup Wiring全解析从双库隔离、渠道默认值两级模型到 OneCLI 集成下一篇PostHog Close CRM 数据源连接器全解析从 API 清单到增量同步的实现细节创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考