企业官网建设流程全解析

前阵子有位读者私信我，说他在准备算法面试时被一道“m*n矩阵中不同路径”难住了：写完递归之后，等了好几分钟都算不出结果，后来换成动态规划又卡在初始化上。我让他顺手把“最小路径和”也做了，结果他惊讶地发现这两道题几乎是同一个模子。这也是我在日常帮别人看代码时最常遇到的情况——很多初学者以为动态规划是一套高深莫测的魔法，实际上，只要你把状态定义写清楚、递推关系弄明白，大部分路径类问题都能用一个统一的模型解决。

这篇文章我会用最直白的方式拆解这两个经典问题：如何从暴力递归进化到记忆化搜索，再改造成二维 DP，最后压缩成一维滚动数组。整个过程不绕弯、不堆术语，每一步我都给出可复现的代码和手算过程。不管你现在是刚接触 DP 的新手，还是已经刷过不少题但总在细节上翻车，这篇内容应该都能帮你把这类问题彻底理清。

1. 为什么这两个问题总被放在一起讲：都是“格子间移动”的决策模型

先别急着写代码，我们试着把问题翻译成“人能看懂的话”。

不同路径的问题描述一般是：一个机器人从左上角出发，每次只能向下或向右移动一格，问到达右下角一共有多少条不同的路径。最小路径和则是在同一个网格里，每个格子上有一个数字，机器人从左上角走到右下角，同样只能向下或向右，问路径上数字之和最小是多少。

这两道题被放在一起，不是因为它们长得很像，而是因为它们共享同一个决策模型：机器人站在某个格子 (i, j) 时，下一步只能往右走到 (i, j+1)，或者往下走到 (i+1, j)。也就是说，如果我们反过来想，要到达格子 (i, j)，机器人只有两种可能的来源——从上方 (i-1, j) 过来，或者从左边 (i, j-1) 过来。

在这个模型下，路径问题天然具有“重叠子问题”和“无后效性”：到达某个格子的方式，只取决于它上方和左方格子的状态，和更早怎么走的无关。这就是动态规划能够发力的地方。很多教程喜欢一上来就抛状态转移方程，搞得大家一头雾水。其实你只要记住一句口诀：“每个格子的答案，是由它上面和左边的答案拼出来的”，后面所有推导都顺理成章。

1.1 先把问题翻译成状态图

我在给朋友讲解的时候，最喜欢画一张 3×3 的网格，把每个格子看成图中的一个节点。从左上角到某个节点的路，只能来自它的上邻居和左邻居。于是整个问题就变成了一个有向无环图，每个节点的入度最多为 2。不同路径问题是在这个图上数从起点到终点的路径数量，最小路径和则是在这个图上找一条总权值最小的路径。

一旦有了这个视角，动态规划的三个关键要素就清晰了：

• 状态：dp[i][j] 表示“从起点走到 (i, j) 的某种结果”，至于是路径数还是最小和，看题目要求。
• 转移：dp[i][j] 由 dp[i-1][j] 和 dp[i][j-1] 两者导出。
• 初始化：起点 (0,0) 的值要单独设置，第一行和第一列因为没有“上方”或“左方”来源，需要特殊处理。

这个模型能解释的还不止这两道题。如果把网格换成棋盘、地图、二维数组，把移动规则从“向右向下”改成“四个方向”，甚至把数字换成概率，核心思路依然通用。这也是为什么我建议路径类 DP 优先从这种“状态图”开始思考，而不是死记代码。

1.2 共同的递推骨架：从上边来 + 从左边来

把两个问题放在一起对比，你会发现它们的状态转移方程长得几乎一模一样：

• 不同路径：dp[i][j] = dp[i-1][j] + dp[i][j-1]
• 最小路径和：dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

唯一的区别只是“合并方式”：一个是加和，因为要累计所有到达该格子的方案数；另一个是取 min，因为要选择代价更小的那一条路。换句话说，动态规划本身只是一个框架，真正决定问题性质的是你对“结果”的定义和对“合并”的选择。

很多人会在这时候问：为什么不能从左上角递归到右下角？其实完全可以，只是纯递归会有大量重复计算。比如计算 (2,2) 时，会去计算 (1,2) 和 (2,1)，而 (1,2) 又要计算 (0,2) 和 (1,1)，这里面 (1,1) 被重复计算的次数呈指数增长。这就是动态规划最核心的价值——把每个子问题的解存起来，避免重复劳动。理解了这一点，后面看代码就会觉得非常自然。

2. 不同路径：计数型DP的完整推导，从递归到填表

不同路径是一个典型的计数问题。所谓“不同路径数”，本质上是把走到每个格子的方案全部加起来。我建议先写一个最暴力的递归版本，哪怕它超时也没关系，因为它能帮助我们看清问题结构。

def unique_paths_naive(m, n): def dfs(i, j): # 越界视为0 if i < 0 or j < 0: return 0 # 起点算1条路径 if i == 0 and j == 0: return 1 return dfs(i - 1, j) + dfs(i, j - 1) return dfs(m - 1, n - 1)

这个写法直白到不能再直白：想到达 (i, j)，就先到达它上方或左边，然后把两条路径数量相加。但当你输入 m=20, n=20 时，这段代码基本就跑不完了。问题出在大量的重复调用：dfs(1,1) 会被 dfs(1,2) 和 dfs(2,1) 分别调用一次，而它们各自又会继续调用相同的子问题。

2.1 先写暴力递归，看它重复计算在哪里

为了更直观地感受重复计算，我拿 m=3, n=3 的调用关系举例。你要计算 dfs(2,2)，它会去算 dfs(1,2) 和 dfs(2,1)。dfs(1,2) 会算 dfs(0,2) 和 dfs(1,1)，dfs(2,1) 会算 dfs(1,1) 和 dfs(2,0)。你看，dfs(1,1) 被算了两次。随着网格边长增加，这个重复量会爆炸式增长，因为每个非边界的格子都会反复出现在大量递归分支里。

解决方式有两种：一是用字典或数组做记忆化，把算过的 dfs(i,j) 存起来；二是直接改成自底向上的循环，这也正是动态规划的标准做法。记忆化搜索本质上还是递归，但能保证每个子问题只算一次；而 DP 用的是迭代填表，逻辑上更显式。两者时间复杂度都是 O(m*n)，但在工程实现上，迭代 DP 通常更少受递归栈深度影响，所以我更推荐初学者先掌握填表法。

2.2 用3×3网格手推一遍DP表

我们手推一个 3×3 的网格，看看 dp 表是怎么一步步填满的。

先初始化：起点 (0,0) 的路径数是 1。第一行 (0,1) 和 (0,2) 只有一条路能到，就是从左边一路走过来，所以全是 1。同理，第一列 (1,0) 和 (2,0) 也只有一条路，所以也全是 1。

初始表如下：

现在按行从上往下填。i=1, j=1 时，它的上方 dp[0][1]=1，左边 dp[1][0]=1，所以 dp[1][1] = 1+1 = 2。i=1, j=2 时，上方 dp[0][2]=1，左边 dp[1][1]=2，所以 dp[1][2] = 1+2 = 3。接着填 i=2 这一行：dp[2][1] = dp[1][1] + dp[2][0] = 2+1 = 3；dp[2][2] = dp[1][2] + dp[2][1] = 3+3 = 6。所以 3×3 网格的不同路径总数是 6。

你可以用穷举法验证：从左上角到右下角，每一步只能向右或向下，总共需要走 2 步右、2 步下，排列组合数是 4!/(2!2!)=6。和 DP 结果一致。这个手算过程虽然简单，但它能让你直观看到“每一格只依赖上方和左方”这一点，这正是后面做空间优化的基础。

2.3 第一行第一列初始化为什么要置1

初始化阶段最容易出错。我见过不少同学把 dp 数组全部初始化为 0，然后从 (0,0) 开始递推，结果第一行和第一列永远是 0，答案自然不对。为什么第一行第一列必须是 1？因为机器人只能向右和向下移动，所以它到达第一行任意格子的路径只有唯一一条：一直向右。第一列同理，只有一直向下这一条。

如果我们在循环里直接dp[i][j] = dp[i-1][j] + dp[i][j-1]，对于 i=0 或 j=0 的格子，会出现下标越界。因此要么单独初始化首行首列，要么在循环里加边界判断。更优雅的做法是让 dp 数组多开一圈，但那样定义状态时就要偏移，代码可读性略差。我个人习惯是直接初始化首行首列，逻辑清晰也不容易出现 bug。

下面是二维 DP 的完整代码：

def unique_paths(m, n): dp = [[0] * n for _ in range(m)] # 初始化第一行和第一列 for j in range(n): dp[0][j] = 1 for i in range(m): dp[i][0] = 1 for i in range(1, m): for j in range(1, n): dp[i][j] = dp[i-1][j] + dp[i][j-1] return dp[m-1][n-1]

这段代码的时间复杂度是 O(m*n)，空间复杂度也是 O(m*n)。对于 m 和 n 几百左右的问题，完全够用。但如果你有空间洁癖，或者面试官追问“能不能把空间优化到 O(n)”，那就要用下一章的滚动数组思路了。

3. 最小路径和：从“数方案”变成“选最优”，DP只是换了个算子

最小路径和看起来只是把加法换成 min，但很多人会在状态定义上犯迷糊。我们沿用同一个网格模型：机器人到达 (i, j) 时，不管之前走的哪条路，到达该格子的路径和一定等于它上一个格子的路径和加上当前格子数值。而上一个格子只有可能是 (i-1, j) 或 (i, j-1)。为了让总路径和最小，我们当然选择两者中较小的那个。这就是“最优子结构”：局部最优的组合能导出全局最优。

注意这里的状态含义变成了“从起点到达当前格子的最小路径和”，而不是“方案总数”。所以转移方程写作：

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

如果你只记住了不同路径的加法，到这里可能反应不过来：为什么要 min？想象你在走山路，走到某个岔路口时，你只需要知道两条路哪条更省力，然后选它。每个格子的决策都是独立的，不会影响后续的“能不能走”，因为无论是从上边来还是从左边来，你到达 (i,j) 之后，下一步往右或往下的选择都一样。这种情况下，min 就是最自然的合并操作。

3.1 先写暴力递归，看它重复计算在哪里

为了验证状态定义，我们同样可以先写一个递归版本：

def min_path_sum_naive(grid): m, n = len(grid), len(grid[0]) def dfs(i, j): if i == 0 and j == 0: return grid[0][0] if i < 0 or j < 0: return float('inf') return grid[i][j] + min(dfs(i - 1, j), dfs(i, j - 1)) return dfs(m - 1, n - 1)

这里越界返回无穷大，是为了让 min 选择另一条有效路径。但因为重复计算，这个递归同样效率低下。给每个格子套一个记忆化，就能看出它其实和不同路径的递归没有本质区别：

from functools import lru_cache def min_path_sum_memo(grid): m, n = len(grid), len(grid[0]) @lru_cache(None) def dfs(i, j): if i == 0 and j == 0: return grid[0][0] if i < 0 or j < 0: return float('inf') return grid[i][j] + min(dfs(i - 1, j), dfs(i, j - 1)) return dfs(m - 1, n - 1)

很多人在写递归时会把起点写成return 0，那是对“路径数”的理解；最小路径和必须返回起点本身的值，因为路径至少包含起点格子。这一步出错会导致所有结果差一个 grid[0][0]。

3.2 手算一个4×4网格的表格

我们用一个具体的 4×4 网格来填表，这样你能看到递推是如果一步一步推进的。

假设网格值如下：

第一步，初始化 dp[0][0] = 1。第一行只能从左边一路累加：dp[0][1]=1+3=4，dp[0][2]=4+1=5，dp[0][3]=5+5=10。第一列只能从上边一路累加：dp[1][0]=1+2=3，dp[2][0]=3+3=6，dp[3][0]=6+6=12。

然后从行1列1开始填：

• (1,1)：grid=8，上方 dp[0][1]=4，左方 dp[1][0]=3，取较小值3，加上8得 11。
• (1,2)：grid=2，上方 dp[0][2]=5，左方 dp[1][1]=11，取5，加2得 7。
• (1,3)：grid=4，上方 dp[0][3]=10，左方 dp[1][2]=7，取7，加4得 11。

继续：

• (2,1)：grid=4，上方 dp[1][1]=11，左方 dp[2][0]=6，取6，加4得 10。
• (2,2)：grid=9，上方 dp[1][2]=7，左方 dp[2][1]=10，取7，加9得 16。
• (2,3)：grid=1，上方 dp[1][3]=11，左方 dp[2][2]=16，取11，加1得 12。

最后：

• (3,1)：grid=5，上方 dp[2][1]=10，左方 dp[3][0]=12，取10，加5得 15。
• (3,2)：grid=7，上方 dp[2][2]=16，左方 dp[3][1]=15，取15，加7得 22。
• (3,3)：grid=2，上方 dp[2][3]=12，左方 dp[3][2]=22，取12，加2得 14。

所以这个网格的最小路径和是 14。你可以自己沿路径验证：1 → 2 → 3 → 4 → 2 → 1 → 2，正好是 14。这个手算过程想说明的是：DP 表里每个格子存的是“到当前格子的最优值”，它并不关心你是从哪条路来的，真正有用的信息只有上方和左方两个候选值。

3.3 网格里有负值、零值时，方法还成立吗

有读者问：如果网格里出现负数和零，min 还适用吗？答案是适用。因为机器人只能向右向下，不能往回走，路径长度是固定的 m+n-2 步。负值只会让某些路径的“成本”变低，但 DP 仍然会从上方和左方选择更小的那个。如果有零，只是不增加成本，不影响递推逻辑。

真正需要注意的场景是：如果允许上下左右任意移动，那就不能再按这个 DP 了，因为会出现回环和无限路径问题，需要改用更复杂的图算法。另外，如果题目要求“必须走完所有格子”或者“路径长度有额外限制”，那状态就要加上更多维度，比如步数或剩余步数。这已经超出了今天讨论的范围，但你要知道核心模型的边界在哪。

4. 空间优化到底怎么想出来的：一行数组滚动的完整推导

二维 DP 虽然好懂，但 m 和 n 一旦到几千，O(m*n) 的空间可能会让内存告急。尤其是面试官经常追问“能不能不用二维数组”，这时候你就得明白空间优化的推导过程，而不是背结论。

我们回头看一看递推表：计算 dp[i][j] 时，只用到了当前行的左边一个 dp[i][j-1] 和上一行的同列一个 dp[i-1][j]。这意味着，当我在填第 i 行时，第 i-2 行及之前的所有数据都不会再被用到。因此，我们完全可以用一维数组 dp[j] 来滚动保存状态：在进入新一行前，dp[j] 存的是上一行第 j 列的值；进入新一行后，从左到右更新 dp[j]，更新后的值就是当前行的值。

4.1 从依赖关系看哪些数据可以扔掉

还是以最小路径和为例。设dp[j]在更新前表示“上一行到第 j 列的最小路径和”。当我们更新dp[j]时，有两个来源：

• 从上方来：就是旧值dp[j]（上一行算出的结果）。
• 从左边来：需要当前行已经更新过的dp[j-1]。

如果我从左到右循环，那么执行到 j 时，dp[j-1] 已经更新为当前行的值，dp[j] 还是上一行的值。于是新dp[j] = grid[i][j] + min(dp[j], dp[j-1])，一行代码就完成了二维 DP 中“上方”和“左方”两个信息的合并。更新完成后，dp[j] 就变成了当前行的值，供下一列使用。

不同路径同理：dp[j] = dp[j] + dp[j-1]，等式右边的 dp[j] 还是上一行到当前列的方法数，dp[j-1] 是当前行已更新的左方案数。这样我们就把空间直接从 O(m*n) 压缩到 O(n)。

4.2 正序更新与逆序更新最容易踩的坑

滚动数组中一个绕不过去的坑是更新方向。拿不同路径来说，我们是在一维数组里正着从左往右更新，因为需要当前行左侧的新值来参与计算。如果你反过来从右往左更新，那么 dp[j-1] 还是上一行的旧值，计算就会出错。这一点和背包问题里的“逆序更新”正好相反，很多同学在这里被搞晕。

判断方法很简单：写出依赖关系。如果某一维的更新会用到当前行已经计算好的值，就必须保证那个值已经被更新。比如不同路径依赖 dp[j-1] 这个“左侧”值，左到右正序能让它先生效；如果依赖的是“右侧”值，那就要右到左。不要死记，画一下状态依赖就能立刻明白。

下面是两个问题的一维滚动版本，可以直接拿去用：

def unique_paths_1d(m, n): dp = [1] * n for i in range(1, m): for j in range(1, n): dp[j] = dp[j] + dp[j-1] return dp[-1] def min_path_sum_1d(grid): if not grid or not grid[0]: return 0 m, n = len(grid), len(grid[0]) dp = [float('inf')] * n dp[0] = 0 for i in range(m): dp[0] += grid[i][0] for j in range(1, n): dp[j] = grid[i][j] + min(dp[j], dp[j-1]) return dp[-1]

注意min_path_sum_1d里 dp 初始化为无穷大，dp[0]=0，这样第一行第一列的值会在循环中被累加。每一行的 dp[0] 单独处理，是因为它只有上方来源，没有左侧来源。如果你不想处理 dp[0] 的边界，也可以用二维 DP 写，但既然选择了空间优化，边界处理就必须格外小心。

4.3 一行代码对比二维DP和一维DP

很多人觉得一维版本“看不懂”，其实只要把二维 DP 的代码和一维放在一起对比，就很容易理解：

• 二维：dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
• 一维：dp[j] = grid[i][j] + min(dp[j], dp[j-1])

唯一的区别是，一维里dp[j]在赋值之前代表dp[i-1][j]，赋值之后代表dp[i][j]。可以说一维数组是“原地更新”，而二维数组是“全量保留”。时间上两者没有差异，都是 O(m*n) 次操作，但一维的空间复杂度从 O(m*n) 降到了 O(n)。

我在实际编码时，会先用二维版本跑通，再手动改成一维。因为二维版本的代码更不容易出错，调试起来也直观。确认逻辑正确后，再根据面试官要求做空间优化。这样做看似多花一步，实际上能帮你省掉大量调试时间。

5. 变体、实战和我的自检清单

动态规划一旦形成框架，最怕的是遇到变体就发怵。其实路径类问题的常见变形，大多是在原模型上加一些限制，比如障碍物、可变移动方向、权重变化等。掌握好这个核心模型，你就能迅速迁移。

5.1 加了障碍物、改变了移动方向怎么办

如果网格中某些格子不能走，也就是“障碍物”，我们只需在状态转移时加一个判断：遇到障碍物，该格子的路径数或最小路径和直接置为 0（对计数题）或无穷大（对最值题），表示不可达或不可选。比如不同路径 II 中，dp[i][j] = 0 if obstacle[i][j] == 1 else dp[i-1][j] + dp[i][j-1]。初始化时，如果第一行或第一列有障碍物，那么障碍物之后的格子全部不可达，都要置 0。

如果移动方向从“只能向右向下”改成“可以向下，也可以向右，还可以斜着走”，那只会在递推公式里多几个来源项，比如dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1]，但模型本身不变。如果改成“可以上下左右走”，那就不是简单的 DAG 了，因为可能出现循环，需要用 Dijkstra 这类图算法，而不是 DP。所以动手前先看清楚题目限制，非常重要。

5.2 组合数学解法与DP的取舍

不同路径还有一种数学解法：从左上角到右下角，无论怎么走，总共需要向右 m-1 步、向下 n-1 步，总共走 m+n-2 步。路径数就是从这 m+n-2 步中选择哪 m-1 步向右，即组合数 C(m+n-2, m-1)。这个公式非常优雅，但有几个问题：一是当 m、n 很大时，组合数计算容易溢出 int，通常需要边计算边约分或使用大数类型；二是如果题目加上障碍物，组合数学会变得极其复杂。DP 则能自然处理障碍物、权重等变体，所以从通用性上来说，我强烈建议大家把 DP 作为主解法，组合数学可以作为验证答案的手段。

比如前面 3×3 的例子里，DP 算出来是 6，组合数 C(4,2)=6，两边一致，你就能对代码更放心。

5.3 我踩过的坑和自检清单

讲几个我实际编码中栽过跟头的地方，也是我在帮别人 review 代码时最常发现的几类问题。

第一，初始化顺序错乱。不同路径里第一行、第一列全置 1，但如果第一行某个格子是障碍物，那就不是无脑置 1 了，必须从障碍物开始变成 0。很多同学把“全都是 1”当成固定套路，遇到变体就翻车。第二，滚动数组遍历方向想当然。比如不同路径的 1D 版本，从左到右更新是没有问题的，但如果题目变成从右下角往左上角走，更新方向就会变。遇到新题一定要先画出依赖关系。第三，最小路径和里忘记加grid[i][j]。状态定义是“路径和”，不是“到了这一步的选择数”，漏加当前格子值会让结果整体变小。第四，处理空网格。grid可能为空或grid[0]为空，很多刷题新手没做防护，直接grid[0][0]崩一地，这个基本功必须养成。

我给自己定了一个自检清单：状态定义是否清楚、边界条件是否覆盖、递推方向是否依赖已更新值、返回结果是 dp[m-1][n-1] 还是 max/min 某一列。每次写完代码，用这几个问题过一遍，能避免绝大部分低级错误。

最后再说一个经验：遇到这类题目，不要急着写代码。先动手画一个 3×3 或 4×4 的例子，把 dp 表格手填一遍，然后观察转移依赖。这个过程能让你少走很多弯路。我过去带过的一位朋友，最初就是靠这个“画表—填表—找依赖”的方法，从看到 DP 就头疼，到后来能在几分钟内写出滚动数组解法。你也不妨试试。