企业官网建设流程全解析

动态规划里有一类问题，刷题的人几乎都绕不过去，就是“m*n矩阵上的路径问题”。标题里写的“不同路径”和“最小路径和”，分别是这类问题里最经典的两个代表：一个问“有多少种走法”，一个问“怎么走总和最小”。我第一次认真啃这两个题的时候，其实挺懵的，因为看起来都是走格子，但一个在数组合数，一个在求最优值，思考的角度完全不一样。后来把它们放在一起对比着做，才真正理解了动态规划里“状态设计”和“转移方程”到底是怎么回事。

这篇文章我想用一套完整的方法论，把这两个问题从头到尾拆开讲清楚。从暴力递归怎么想到动态规划，到状态转移方程怎么列，再到空间怎么优化，最后附上我实际写代码时踩过的坑和排查经验。无论你是刚接触动态规划的新手，还是想系统梳理这类题型的进阶选手，这篇文章都能给你一份可以直接照着练、照着改的参考。

1. 两个问题到底在问什么

很多人一看到“m*n矩阵”就开始套模板，结果两个题混着做，越做越乱。先别急着写代码，我们花点时间把题意彻底搞清楚。

1.1 “不同路径”的本质是计数问题

“不同路径”这个题，典型描述是这样的：一个机器人位于m行n列的矩阵左上角，每次只能向右或者向下移动一步，问到达右下角一共有多少条不同的路径。

这个题的核心字眼是“多少条”。它不关心你走的路哪条更短、哪条更省体力，它只关心你从头到尾能走出几种不同的走法。比如一个2行3列的矩阵，从左上角到右下角，所有可能的走法都要被数出来，一条都不能漏。

从数学上看，这其实是个组合问题。因为每次只能向右或向下，总共要走(m-1)次向下、(n-1)次向右，一共(m+n-2)步，问题等价于从这(m+n-2)步中选哪几步是向下的，所以答案就是组合数C(m+n-2, m-1)。但在面试场景里，面试官往往希望看到的是动态规划的推导过程，而不是直接甩一个组合数公式。为什么？因为组合数公式只能解决无阻碍的满矩阵，一旦矩阵里加了障碍物，公式就失效了，而动态规划的思路可以无缝扩展。

1.2 “最小路径和”的本质是优化问题

“最小路径和”这个题，矩阵里每个格子都有一个非负的数字，路径从左上角到右下角，每次只能向右或向下移动，路径上经过的所有格子数字之和就是这条路径的“代价”，要求找出所有路径中数字总和最小的那条。

这里核心字眼是“最小”。它不关心有多少条路可以走，只关心哪条路的花费最少。因为每个格子都有不同的数字，同一个格子，从不同的方向走过来，累计代价是不一样的，所以我们每一步都需要做一个决策：到底是从左边过来划算，还是从上边过来划算。

这两个题放在一起，正好对应了动态规划里两类基本问题：一类是“计数型DP”，一类是“最值型DP”。它们的套路框架完全一样，都是“状态定义 + 状态转移 + 初始化 + 遍历顺序”，但思考的落脚点不同：一个在数方案数，一个在比大小。理解了这一点，你就抓住了这两个题的根本区别，后面所有的代码都是从这一个区别派生出来的。

1.3 为什么这两个题值得放在一起学

单独做任何一个题，你可能背一遍代码就过了，但很难形成体系。放在一起对比，才能看到动态规划里更本质的东西：

• 状态定义都是“dp[i][j]代表到达(i,j)时的某种信息”；
• 转移方向都是“只能从左边和上边来”；
• 遍历顺序都是“从上到下，从左到右”；
• 边界处理都是“第一行和第一列只能单向走”。

既然框架高度一致，那唯一的区别就集中在“dp[i][j]存的是什么”以及“转移的时候做什么运算”。我见过太多人把这两个题做完就扔，其实只要花半小时对比复盘，动态规划的地基就能打得非常扎实，后面再做编辑距离、背包问题，理解速度都会快很多。

2. 动态规划解题框架：从暴力递归到状态转移

很多教程上来就给你状态转移方程，然后说“你看，这不是很简单吗”。但实际遇到新题的时候，你根本不知道方程怎么来的。我自己的经验是，与其硬记方程，不如先走一遍“暴力递归 → 记忆化搜索 → 递推DP”的思考路径，这样方程就是自己长出来的，而不是背下来的。

2.1 暴力递归：先想清楚“我从哪里来”

动态规划的所有状态转移，本质上都能从递归的角度理解。以最小路径和为例，假设我定义函数dfs(i, j)表示“从(i,j)出发到右下角的最小路径和”，那么站在(i,j)这个位置，我有两个选择：往右走到(i,j+1)，或者往下走到(i+1,j)。我需要选择“更划算”的那条路，再加上当前格子的数字。

递归关系就出来了：

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

如果你愿意，也可以换个角度，把dfs(i, j)定义为“从左上角到(i,j)的最小路径和”，那状态转移就是：

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

两种定义都能做，区别只在于遍历方向和思考习惯。我个人更习惯用“从左上角到(i,j)”这个正向定义，因为写递推循环的时候更符合大脑的阅读顺序，从上到下、从左到右扫过去，非常顺。

2.2 记忆化搜索：让递归不再重复计算

暴力递归的问题是，同一个(i,j)会被重复计算很多次。比如你从两条不同路径都能到达(2,2)，那dfs(2,2)就会被调用两次，每次都要把后面整棵递归树重新算一遍。m和n稍微大一点，比如50乘50，运行时间就会爆炸。

解决办法很朴素：用一个二维数组memo把已经算过的结果存起来，下次再遇到dfs(2,2)的时候直接返回memo[2][2]，不用再递归展开。这就是记忆化搜索，本质上已经是动态规划了，只是代码形态上是递归的。对某些状态转移顺序比较诡异的问题，记忆化搜索比递推更好写，因为不用手动设计遍历顺序，递归的自然顺序就是对的。

2.3 递推DP：把递归改成循环

记忆化搜索虽然逻辑清晰，但在工程上，递归有函数调用开销，深度大了还可能栈溢出。所以更通用的是递推写法：用一个dp数组，按顺序从小到大把每个状态算出来，每个状态只算一次。

这里最关键的思考是：既然每个状态依赖它“左边”和“上边”的状态，那我只要保证在计算dp[i][j]的时候，dp[i-1][j]和dp[i][j-1]都已经算好了就行。按行遍历、每行从左到右，天然满足这个条件。这就是为什么这类矩阵路径题的遍历顺序几乎是固定的，不需要像某些区间DP那样绞尽脑汁设计顺序。

从暴力递归到记忆化搜索再到递推DP，这条演进路线我建议每个人都亲手走一遍。走完你对“状态转移方程是怎么来的”这个问题，就再也不会发怵了。面试的时候被问到，也能讲得头头是道，而不是只能说“我是背的模板”。

3. 不同路径的完整推导与代码实现

现在我们正式进入第一个题。我先讲状态定义和转移方程，再给出完整代码，最后展示几种不同的实现层次，你可以根据自己的阶段选择掌握。

3.1 状态设计与转移方程

定义dp[i][j]表示从左上角(0,0)到达(i,j)的不同路径数。

思考“怎么到(i,j)”：因为每次只能向右或者向下走，所以要到达(i,j)，只能从它的上方(i-1,j)往下走一步，或者从它的左边(i,j-1)往右走一步。所以：

dp[i][j] = dp[i-1][j] + dp[i][j-1]

这就是整个题最核心的公式，没有别的了。

边界条件怎么处理？看第一行：第一行的格子只能从左边走过来，因为没有上方，所以dp[0][j]恒等于1。同理，第一列的格子只能从上方走下来，dp[i][0]恒等于1。起点dp[0][0]，按这个规则也就是1，因为它本身就算一条“原地”路径的起点，不需要移动就到达了。

这里有一个初学者容易纠结的地方：为什么第一行全部是1而不是越来越大？比如dp[0][2]为什么不是dp[0][1]加什么东西？因为从(0,0)到(0,2)，你只能一路向右，没有任何别的选择，所以路径数就是1条。你不可能在只能向右的情况下走出第二条不同的路线。这个逻辑确认清楚，边界就不会写错。

3.2 基础版代码实现

直接按照上面的公式写，两层循环搞定。我用Python演示，因为可读性最好，你理解以后换成Java或Go都很容易。

def unique_paths(m, n): # dp[i][j] 表示到达 (i, j) 的路径数 dp = [[0] * n for _ in range(m)] # 第一列：只能从上往下走，路径数都是 1 for i in range(m): dp[i][0] = 1 # 第一行：只能从左往右走，路径数都是 1 for j in range(n): dp[0][j] = 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)。m=3, n=7的时候输出是28，你可以手动画一画，验证一下这个结果对不对。画的时候你会发现，矩阵里的数字呈现出一种很有规律的排列，像极了杨辉三角，这正是组合数公式成立的原因。

3.3 空间优化：滚动数组

如果面试官追问“能不能把空间复杂度降到O(n)”，你就该拿出滚动数组了。观察状态转移方程dp[i][j]只依赖dp[i-1][j]（上一行的同一列）和dp[i][j-1]（当前行的前一列），这意味着我们根本不需要把整个二维矩阵都存下来，只要保留一行数据就够了。

用一个一维数组dp，长度为n，每次更新的时候，dp[j]代表“当前行第j列的值”。更新逻辑是：

dp[j] = dp[j] + dp[j-1]

等等，这个式子是什么意思？等式右边的dp[j]是上一行遗留下来的值，也就是dp[i-1][j]；dp[j-1]是当前行刚更新过的值，也就是dp[i][j-1]。两个一加，正好是dp[i][j]。然后把这个新值存回dp[j]，覆盖掉上一行的旧值。整个过程就是原地更新，非常优雅。

def unique_paths_optimized(m, n): dp = [1] * n # 第一行全为 1 # 从第二行开始逐行更新 for i in range(1, m): for j in range(1, n): dp[j] = dp[j] + dp[j-1] return dp[n-1]

这里有个细节值得注意：内层循环从j=1开始，不能从0开始。因为dp[0]始终代表第一列，永远等于1，不需要更新也不能更新，否则算法就乱了。同理，如果m和n的大小关系不固定，你可以选较小的那个做列数，把空间压到min(m, n)，细节是遍历前先判断一下，让外层循环走较大的维度，内层走较小的维度，这样空间更省。实测下来，这种优化在m和n都很大的时候效果非常明显，比如10000乘10000的矩阵，二维数组根本开不出来，一维数组轻松搞定。

3.4 组合数学的直接解法

既然前面提到了组合数公式，这里也顺便说一下，如果你只是为了快速求出答案，可以用数学方法：

answer = C(m+n-2, m-1)

展开就是(m+n-2)! / ((m-1)! * (n-1)!)。为了避免阶乘溢出，通常用累乘的方式边乘边除：

def unique_paths_math(m, n): # 总共需要走的步数 total = m + n - 2 k = min(m - 1, n - 1) # 计算 C(total, k)，用累乘避免大数阶乘 result = 1 for i in range(1, k + 1): result = result * (total - k + i) // i return result

这个技巧的核心是约分，每乘一个数就除一次，保证中间结果不会太大。但我要提醒一句：这个公式只适用于矩阵中没有障碍物的情况。一旦题目改成“某些格子不能走”，组合数学就直接失效了，你必须回到动态规划。所以动态规划才是这个题的通用正解，数学方法只能作为一个补充技巧。

4. 最小路径和的完整推导与代码实现

第二个题，和第一个题共享同一个矩阵框架，但状态里存的是“累计代价”。这个题在实际工作中更常见，因为很多东西都能抽象成“走格子求最小代价”，比如编辑距离、计算两个字符串的相似度，本质上都是类似的路径选择问题。

4.1 状态设计与转移方程

定义dp[i][j]表示从左上角(0,0)到达(i,j)的路径上所有数字的最小总和。

同样的道理，要到达(i,j)，你只能从上方或者左边过来。不同的是，这里比的不是“几条路”，而是“哪条路的代价更小”。所以状态转移方程是：

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

翻译成大白话就是：到达(i,j)的最小代价，等于当前格子的数字，加上“从上面来”和“从左边来”两者中较小的那个累计代价。

边界条件怎么处理？第一行：只能从左边过来，所以dp[0][j] = dp[0][j-1] + grid[0][j]，是累加的关系。注意这里不再是恒等于1了，因为每个格子的数字不同，累计值会一直变大。第一列同理，dp[i][0] = dp[i-1][0] + grid[i][0]。

这个边界条件的差异，正是两个题最明显的表象区别。很多人把不同路径的边界“全是1”记熟了，做到最小路径和还写1，结果全都算错。归根到底，还是要回到问题本身去理解边界，而不是死记规则。

4.2 基础版代码实现

直接上二维dp版本，逻辑最清晰，作为第一版肯定够用：

def min_path_sum(grid): m = len(grid) n = len(grid[0]) # 复制一份作为 dp，避免修改原数组 dp = [[0] * n for _ in range(m)] dp[0][0] = grid[0][0] # 初始化第一行 for j in range(1, n): dp[0][j] = dp[0][j-1] + grid[0][j] # 初始化第一列 for i in range(1, m): dp[i][0] = dp[i-1][0] + grid[i][0] # 填充剩余部分 for i in range(1, m): for j in range(1, n): dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]) return dp[m-1][n-1]

这个代码的复杂度也是O(mn)的时间、O(mn)的空间。注意我用了独立的dp数组，而不是直接改原数组，主要是为了保留原始数据，方便调试的时候打印对照。如果面试官不要求，其实直接原地改grid也行，能省不少空间。

4.3 空间优化：原地修改

最小路径和的“原地修改”优化非常巧妙。因为每个dp[i][j]更新完之后，原来的grid[i][j]就再也没有用了，所以可以直接把结果写回grid[i][j]，省掉整个dp数组。

def min_path_sum_inplace(grid): m = len(grid) n = len(grid[0]) # 初始化第一行 for j in range(1, n): grid[0][j] += grid[0][j-1] # 初始化第一列 for i in range(1, m): grid[i][0] += grid[i-1][0] # 原地填充 for i in range(1, m): for j in range(1, n): grid[i][j] += min(grid[i-1][j], grid[i][j-1]) return grid[m-1][n-1]

这个版本的空间复杂度是O(1)，因为除了原数组外我们没有额外开销。我第一次写出这个优化的时候，真的觉得动态规划太精妙了，同样的结果，空间从二维变成零。但也要注意，原地修改有副作用：调用完这个函数，你的原始矩阵就没了。如果后面还要用原始数据做其他计算，就别用这个版本。工程上“不修改输入”是好习惯，面试时主动提一句“我也可以用原地修改，但为了保留原始数据我选择另开数组”，会加分。

4.4 一维滚动数组版本

如果你不想修改原数组，又想省空间，那就用滚动数组。这里有个细节比“不同路径”稍微复杂一点：第一行的初始化不能简单全设成第一个格子，而是要累加。我给出完整版本：

def min_path_sum_roll(grid): m = len(grid) n = len(grid[0]) # dp[j] 表示当前行第 j 列的最小路径和 dp = [0] * n dp[0] = grid[0][0] # 初始化第一行：只能从左往右走 for j in range(1, n): dp[j] = dp[j-1] + grid[0][j] # 逐行更新 for i in range(1, 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[n-1]

这个版本里，dp[j]在更新之前存的还是上一行的值，也就是“从上面下来的路径和”，dp[j-1]已经在当前行更新过了，也就是“从左边过来的路径和”，取较小值再加上当前格子的数字，正好就是状态转移方程。空间O(n)，非常好用。说实话，在我见过的面试解答里，能把这个版本一气呵成写出来的人，动态规划的基本功基本都不差。

5. 常见问题与排查技巧实录

代码写多了，总会遇到一些看起来莫名其妙的问题。我把实际调试过程中频率最高的几个坑集中整理一下，每一条都是血泪教训，建议你对照自查。

5.1 问题一：边界初始化顺序反了

我见过最多的错误，是把第一行和第一列的初始化写在填充循环之后，或者干脆忘了写。如果忘了初始化第一行，dp[0][j]会一直是0，那min(dp[i-1][j], dp[i][j-1])就会错误地选择这一路，导致结果偏小。如果忘了初始化第一列，则是同样的道理。

正确做法是在填充主循环之前，先把第一行和第一列全部处理好。不管是不同路径的“置1”，还是最小路径和的“累加”，都必须提前完成。这里有一个排查技巧：如果你发现结果比预期小很多，十有八九就是边界没有正确初始化。打印出dp数组看一眼，边界全是0的基本就是这个问题。

5.2 问题二：滚动数组更新时读取了被污染的数据

滚动数组虽然省空间，但写起来有个大坑：当前行在更新的时候，j-1位置的数据已经被新值覆盖了。这在最小路径和问题里是没问题的，因为我们需要的就是当前行的dp[j-1]；但在某些更复杂的问题里，如果你希望读到上一行的旧值，就必须把“上一行”和“当前行”两个字分开存，可以用两个一维数组交替。

判断标准很简单：看状态转移方程里依赖的是dp[i-1][j]还是dp[i][j-1]。如果两个都要用，且其中一个必须是旧值，就要特别小心更新顺序。我的习惯是：能不优化空间就不优化，先写二维版本验证逻辑，确认无误后再改成滚动数组。宁可多写几行，不要一上来就炫技，结果调了半天才发现是数据污染。

5.3 问题三：m和n为1时的边界情况

如果矩阵只有1行或者只有1列，比如m=1, n=5，那么机器人只能一直向右走，路径数只有1；最小路径和则是整行数字的总和。

你的代码必须能正确处理这种情况。很多人的代码在m=1或n=1时会越界，因为循环里访问了grid[1][0]或者grid[0][1]。排查方法很简单：函数开头加一个判断，如果m==1或者n==1，直接返回唯一路径的答案。不要小看这种边界case，面试时很多题不是错在核心逻辑，而是挂在边界用例上。

5.4 问题四：数值溢出

不同路径的答案增长非常快。比如m=25, n=25的时候，路径数大概是2.4e14，已经接近32位整数的上限了。如果你用C++的int来存，直接溢出变成负数。所以：

• C++/Java用long long，对应Java的long，Python因为是大整数，天然无此烦恼；
• 但也要注意，某些变种题目的中间结果可能比最终答案还大，计算过程中就要用更大范围的类型；
• 最小路径和的数字加和一般不会太大，但如果你处理的是带负权的格子，min操作可能会选出负数路径，也要提前想清楚业务逻辑允不允许负值。

一个小技巧：写完代码以后，用最大的m、n测一遍，看结果是不是正数且合理。如果出现负数或者明显不合理的数字，第一时间检查类型，不要怀疑公式写错了。

5.5 问题五：把两个题的解法搞混了

最后这个坑听起来很蠢，但绝对不是少数。很多人刷题刷多了，状态转移方程写串了：求不同路径的时候用了min，求最小路径和的时候用了加法。

怎么避免呢？我自己的心法是：读完题先问自己一句“这个题是问多少条，还是问多少值”？答案是“多少条”就用累加；“多少值”就用min/max。把这句话写在题目前面，每次写代码前大声念一遍。你要是能坚持这个习惯三个月，基本不会再犯这种错误。

5.6 问题排查速查表

我把上述问题和对应的排查方向整理成一张表，方便你贴在电脑前或者记在笔记里：

这张表是我自己在刷题复盘时慢慢积累的，不一定覆盖所有bug，但覆盖了最常见的80%。遇到问题先对着表看一遍，能省不少时间。

6. 延伸思考：从这两个题到更复杂的动态规划

如果你把上面两个题都彻底搞懂了，恭喜你，你已经掌握了动态规划里最基础也最重要的一类模型：网格路径模型。这个模型可以延展出很多变种，提前了解一下，后面遇到就不会慌。

6.1 加了障碍物的路径问题

最常见的变种是“不同路径 II”：矩阵里某些格子是障碍物，不能走。解法其实很简单，只要在状态转移的时候加一个判断：如果当前格子是障碍物，dp[i][j]直接等于0；否则正常按公式计算。边界也一样，第一行如果遇到障碍物，后面全部为0，因为被堵住了。

这类变种能帮你进一步理解“初始化和转移并不是死公式，而是要根据题目语义动态调整”这一思想。遇到新题的时候，不要急着套模板，先想想“我这个状态到底代表什么意思，障碍物对它有什么影响”。

6.2 从矩阵到字符串：编辑距离问题

编辑距离是动态规划里另一个经典题：把字符串A变成字符串B，最少需要多少次增删改操作。如果你仔细看它的状态转移方程，本质上是在一个(m+1)*(n+1)的矩阵里找一条代价最小的路径，只是每个格子代表的是两个字符串前缀的匹配情况。

有了最小路径和的基础，再看编辑距离，你会发现思路是相通的：都是定义dp[i][j]表示“前缀i和前缀j之间的关系”，都是考虑“从上方、左方、左上角过来”三种方向的选择。区别只是每个方向的代价不同、操作语义不同。所以我说，矩阵路径这两个题不仅仅是两个题，它们是理解一大类字符串DP的敲门砖。

6.3 从二维到多维的推广

如果你想挑战更复杂的，可以考虑“三维路径DP”，比如在三维网格中求路径数。虽然维度多了一维，但思考方式完全一样，状态变成dp[i][j][k]，转移方向从两个变成三个，其他照旧。这就体现了“状态定义做扎实，后面维度扩展只是体力活”这句话。

我个人刷动态规划的经验是：不要贪多，先把二维网格这类最基础的模型吃透。你把不同路径、最小路径和、带障碍物版本、最大正方形这几道题做熟、做透，面试考动态规划的基础题基本就稳了。剩下的全是排列组合式的变体，万变不离其宗。

最后分享一个我自己常用的调试技巧：每次写完动态规划的代码，先用一个超小的用例手动模拟一遍整个dp数组的填充过程，哪怕慢一点也要画一遍。这一步做完，你不仅是在验证代码，更是在加深对状态转移的理解。很多看似“灵光一现”的点评，其实都是这样一笔一笔画出来的手感。刷题这种事，从来没有捷径，但如果你每一步都走得很扎实，后面真的会越走越快。