企业官网建设流程全解析

• 示例工程

本篇技术指南以 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

约束条件

说明：本题与主站 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 > 0）：

dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

算法流程

1. 初始化dp二维数组，并将dp[0][0]置为grid[0][0]；
2. 按行方向预处理第一列的累加和；
3. 按列方向预处理第一行的累加和；
4. 双重循环遍历内部格子，套用上述递推公式；
5. 返回dp[m-1][n-1]。

复杂度：时间复杂度O(m × n)（每个格子只被计算一次），空间复杂度O(m × n)（需要一张与网格同尺寸的 DP 表）。其中m、n分别为网格行数与列数。

四、多语言实现

以下实现均完整取自仓库对应目录，可直接提交运行。

Python3

class 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]

Java

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]; } }

C++

class Solution { public: int minPathSum(vector<vector<int>>& grid) { int m = grid.size(), n = grid[0].size(); vector<vector<int>> dp(m, vector<int>(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]; } };

Go

func 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] }

TypeScript

function 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]; } }

Swift

class 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 = grid），Rust 版本则声明mut grid后直接累加：

impl Solution { pub fn min_path_sum(mut grid: Vec<Vec<i32>>) -> 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 混合场景。

掌握最小路径之和这道题后，你对"最优子结构 + 重叠子问题"的理解会自然迁移到上述兄弟题目中，刷题效率将显著提升。

• 示例工程