1. 从“爬楼梯”到“网格路径”为什么路径计数是动态规划的最佳练兵场很多人学动态规划第一道题是爬楼梯第二道题是零钱兑换第三道题就卡住了。问题出在哪儿出在爬楼梯太特殊了——它只有一个维度状态转移只跟前面一两个状态有关你甚至可以用两个变量滚动更新连数组都不用开。这种题做多了会产生一种“动态规划不过如此”的错觉等到遇见二维网格、多阶段决策、带障碍物的路径计数立刻被打回原形。路径总数问题恰好卡在“简单”和“复杂”之间。说它简单是因为状态定义几乎写在题面上从起点走到某个格子有多少种走法。说它复杂是因为它强迫你建立二维的状态空间强迫你思考边界条件强迫你处理障碍物带来的状态不可达问题。更关键的是路径计数问题有一个非常直观的几何解释——你走的每一步都在“消耗”一个维度上的剩余步数这种“资源消耗”的视角是理解更复杂动态规划问题的钥匙。我见过太多人做动态规划的方式是“背转移方程”。看到网格就写dp[i][j] dp[i-1][j] dp[i][j-1]看到字符串就写dp[i][j] dp[i-1][j-1] 1。方程背对了题也过了但下次换个场景又不会。根本原因在于他们没有想清楚“状态到底在描述什么”。路径计数问题最大的价值就是逼你把这件事想清楚dp[i][j]不是“走到(i,j)的走法数”这么简单它背后隐含的是“所有从起点到(i,j)的合法路径集合的基数”。这个集合是怎么构成的是由“最后一步从上面来”的路径集合和“最后一步从左边来”的路径集合做并集得到的。因为最后一步不同这两个集合不相交所以总数可以直接相加。这个“集合划分”的思想才是动态规划的精髓。路径计数只是它最朴素的表现形式。你把这个思想吃透了后面做背包问题、编辑距离、最长公共子序列都会有一种“原来都是在做集合划分”的通透感。这篇文章我会从最基础的网格路径计数出发一步步扩展到带障碍物、带权值、多阶段决策的变体重点不是给你一堆代码而是把每一步的“为什么”讲清楚。适合已经写过几道动态规划题但总觉得差点意思的读者也适合想从路径计数这个切口重新理解动态规划的从业者。2. 网格路径计数的状态定义为什么dp[i][j]能表示走法总数2.1 从“走法”到“状态”的抽象过程先看最经典的场景一个m行n列的网格从左上角(0,0)出发每次只能向右或向下走一步问到右下角(m-1,n-1)一共有多少种不同的路径。很多人第一反应是“这题我会”然后直接写代码。但我想先停下来问一个问题为什么可以用一个二维数组来表示“走法总数”走法是一个过程是一个序列怎么用一个数字概括关键在于“无后效性”。当你站在格子(i,j)上时你关心的是“从起点走到这里有多少种走法”而不关心“这些走法具体长什么样”。因为无论你之前怎么走的接下来能走的步骤只取决于你当前的位置——你只能向右或向下跟历史路径无关。这就是无后效性当前状态包含了做出下一步决策所需的全部信息。所以dp[i][j]的定义是从起点(0,0)走到格子(i,j)的所有合法路径的数量。注意这里说的是“数量”不是“路径本身”。我们用一个整数来代表一个集合的基数这是动态规划最核心的压缩思想。2.2 状态转移方程的推导集合的划分与相加有了状态定义接下来推导转移方程。走到(i,j)的最后一步只有两种可能从上面(i-1,j)向下走一步或者从左边(i,j-1)向右走一步。这里有一个容易被忽略的逻辑细节为什么这两种情况的路径数可以直接相加因为“最后一步从上面来”的所有路径和“最后一步从左边来”的所有路径是两个不相交的集合。一条路径不可能最后一步既从上面来又从左边来。既然不相交那么总集合的大小就等于两个子集大小之和。用公式表示就是dp[i][j] dp[i-1][j] dp[i][j-1]这个方程看起来简单但它包含了动态规划的两个基本操作划分和合并。划分是把大问题拆成互不相交的子问题合并是把子问题的解组合成原问题的解。你后面学背包问题划分方式是“选或不选第i个物品”学编辑距离划分方式是“删除、插入、替换”。形式不同本质一样。2.3 边界条件的处理第一行和第一列为什么只有一种走法转移方程里用到了dp[i-1][j]和dp[i][j-1]当i0或j0时会出现越界。所以需要单独处理边界。对于第一行i0你只能一直向右走没有任何其他选择所以dp[0][j] 1。同理第一列j0只能一直向下走dp[i][0] 1。起点dp[0][0] 1表示“站在原地”这一种走法。这里有一个常见的错误把dp[0][0]初始化为0。如果起点是0那么整个数组都会是0因为所有值都是从起点累加出来的。另一个错误是忘记初始化第一行和第一列导致转移方程在边界处取到默认值0结果偏小。注意边界初始化不是“特殊情况”而是状态定义在边界上的自然结果。第一行只有一种走法是因为从(0,0)到(0,j)只有一条水平路径这是客观事实不是人为规定。2.4 从小规模实例手推验证拿一个3x3的网格手动推一遍能帮你建立直觉。网格坐标从(0,0)到(2,2)。第一行全是1dp[0][0]1, dp[0][1]1, dp[0][2]1。 第一列全是1dp[1][0]1, dp[2][0]1。然后逐个填dp[1][1] dp[0][1] dp[1][0] 1 1 2dp[1][2] dp[0][2] dp[1][1] 1 2 3dp[2][1] dp[1][1] dp[2][0] 2 1 3dp[2][2] dp[1][2] dp[2][1] 3 3 6最终答案是6。你可以手动枚举验证从(0,0)到(2,2)需要向右走2步、向下走2步总共4步选择其中2步向下的位置组合数C(4,2)6。结果吻合。这个组合数的视角很重要。当没有障碍物时路径总数就是组合数C(mn-2, m-1)。动态规划的解法本质上是在计算这个组合数只不过用递推的方式避免了阶乘溢出。理解这一点你就能明白为什么动态规划在这个问题上是“用空间换时间”的——它把组合数的计算拆成了一个个小规模的加法。3. 带障碍物的路径计数状态不可达时该怎么处理3.1 障碍物改变了什么从“全部可达”到“部分不可达”基础版的网格路径计数有一个隐含假设所有格子都是可达的。但现实中网格上可能有障碍物比如某些格子不能通过。这时候状态的定义需要微调dp[i][j]表示从起点走到(i,j)且不经过任何障碍物的路径数量。如果(i,j)本身是障碍物那么dp[i][j] 0因为没有任何合法路径能停在一个障碍物上。这个0不是“没有路径”而是“这个状态本身就不合法”。区别在于对于可达的空格子dp值是正数对于障碍物dp值强制为0表示这个状态被“禁用”了。3.2 转移方程在障碍物处的修正转移方程的形式不变仍然是dp[i][j] dp[i-1][j] dp[i][j-1]但前提是(i,j)不是障碍物。如果是障碍物直接跳过保持0。这里有一个容易踩的坑边界初始化。第一行和第一列不再全是1了。如果第一行中间有一个障碍物那么障碍物之后的所有格子都不可达dp值应该是0。因为从起点出发只能向右走一旦遇到障碍物就过不去了。举个例子第一行是[起点, 空格, 障碍, 空格]。dp[0][0]1, dp[0][1]1, dp[0][2]0障碍物dp[0][3]0因为从左边来的路被障碍物堵死了从上面来又不存在。所以边界初始化需要逐个判断如果当前格子是障碍物dp0否则如果是最左边或最上面dp等于前一个格子的dp值。3.3 一个具体的障碍物网格推演假设3x3网格障碍物在(1,1)。坐标从(0,0)到(2,2)。初始化dp[0][0]1, dp[0][1]1, dp[0][2]1第一行无障碍dp[1][0]1, dp[2][0]1第一列无障碍填表dp[1][1]是障碍物dp0dp[1][2] dp[0][2] dp[1][1] 1 0 1dp[2][1] dp[1][1] dp[2][0] 0 1 1dp[2][2] dp[1][2] dp[2][1] 1 1 2答案是2。手动验证从(0,0)到(2,2)必须经过(1,1)吗不一定。路径可以是(0,0)-(0,1)-(0,2)-(1,2)-(2,2)或者(0,0)-(1,0)-(2,0)-(2,1)-(2,2)。这两条路都绕开了(1,1)。其他路径都会经过(1,1)所以只有2条。结果正确。3.4 障碍物问题的实操心得在实际写代码时我习惯把障碍物格子的dp值在初始化阶段就设为0然后在填表循环里加一个判断如果当前格子是障碍物直接continue。这样代码逻辑清晰不容易出错。另一个经验是不要试图在转移方程里处理障碍物。有些人会写成dp[i][j] (isObstacle[i][j] ? 0 : dp[i-1][j] dp[i][j-1])这样写没问题但可读性差。更好的做法是把障碍物的判断提前让转移方程保持最简形式。还有一个边界情况如果起点或终点本身就是障碍物直接返回0。这个判断要放在最前面否则后面的初始化逻辑会变得很别扭。4. 路径计数的空间优化从二维数组到一维滚动4.1 为什么可以压缩空间状态依赖的方向性标准的二维dp需要O(m*n)的空间。但观察转移方程dp[i][j] dp[i-1][j] dp[i][j-1]你会发现计算第i行时只依赖第i-1行的数据和当前行左边的数据。也就是说第i-2行及更早的数据在计算完第i-1行后就不再需要了。这意味着我们可以用一个一维数组来滚动更新。具体做法是维护一个长度为n的数组dpdp[j]在更新前代表上一行i-1行第j列的值更新后代表当前行i行第j列的值。更新顺序必须是从左到右。因为dp[j] dp[j]上一行的值 dp[j-1]当前行已更新的值。如果从右到左更新dp[j-1]还是上一行的值就错了。4.2 一维数组的初始化和更新细节初始化dp[0] 1起点其余dp[j] 1第一行只有一种走法。如果有障碍物遇到障碍物时dp[j] 0并且后续的dp值要相应调整。更新过程用代码表示for i in range(m): for j in range(n): if obstacle[i][j]: dp[j] 0 elif j 0: dp[j] dp[j] dp[j-1] # j 0 时dp[0]保持不变第一列只有一种走法注意j 0的情况dp[0]在每一行都应该是1如果没有障碍物因为它代表第一列只能一直向下走。但在有障碍物的情况下如果第一列某个格子是障碍物dp[0]要变成0并且后续行的dp[0]也保持0。4.3 空间优化的收益与代价空间从O(m*n)降到O(n)当n很大时收益明显。但代价是代码可读性下降调试难度增加。我的建议是如果是面试或竞赛先写二维版本确保逻辑正确再考虑优化。如果是生产环境空间优化带来的性能提升通常不值得牺牲可维护性除非m和n确实非常大。还有一个细节如果m n可以交换行列让一维数组的长度取较小值进一步节省空间。这个技巧在矩阵很大的时候有用但要注意交换后障碍物的坐标也要相应转置。5. 路径计数的变体带权值、多阶段与组合数学视角5.1 带权值的最小路径和从计数到优化路径计数是“有多少种走法”带权值的最小路径和是“哪种走法代价最小”。状态定义从“数量”变成“最小值”转移方程从“相加”变成“取最小再加当前权值”。dp[i][j] min(dp[i-1][j], dp[i][j-1]) grid[i][j]这个变体看起来只是把加法换成min但它代表了一类重要的动态规划问题最优化问题。计数问题是“求和”优化问题是“求极值”。两者的共同点是都需要划分状态空间区别在于合并方式不同。在实际操作中带权值问题的边界初始化要注意第一行和第一列不再是1而是累加值。dp[0][j] dp[0][j-1] grid[0][j]因为只有一条路可走代价就是沿途权值之和。5.2 多阶段决策每一步有多个选择的情况如果网格中每个格子可以向多个方向走比如四个方向问题就变成了图上的路径计数。这时候动态规划可能不再适用因为状态之间可能存在环不满足无后效性。你需要用记忆化搜索或者拓扑排序来处理。但如果方向仍然是向右和向下只是每一步可以选择走1步或2步那么状态转移方程会变成dp[i][j] dp[i-1][j] dp[i-2][j] dp[i][j-1] dp[i][j-2]这本质上是在更大的步长上做划分。理解了这个你就能明白为什么动态规划的转移方程可以灵活调整——只要你能保证子问题不相交且覆盖所有情况。5.3 组合数学视角什么时候不需要动态规划当没有障碍物时路径总数就是组合数C(mn-2, m-1)。这个公式的推导很简单总共需要走mn-2步其中m-1步向下n-1步向右选择哪些步向下即可。那为什么还要用动态规划因为组合数计算涉及大数阶乘容易溢出而且当有障碍物时组合数公式不再适用。动态规划的优势在于它天然处理障碍物和权值而且递推过程中数字增长是渐进的不容易溢出当然如果路径数太大仍然需要取模。在实际工程中如果确认没有障碍物且m、n不大直接用组合数公式更快。但如果有任何不确定性动态规划是更稳妥的选择。6. 动态规划解题思路的通用框架从路径计数中提炼6.1 状态定义的三个要素位置、约束、目标路径计数问题的状态定义包含三个要素位置(i,j)、约束只能向右或向下、目标到达终点的路径数。推广到一般动态规划问题状态定义需要明确当前处于哪个阶段位置有哪些限制条件约束需要优化或计算什么目标。很多动态规划题难就难在状态定义。比如背包问题状态是“前i个物品在容量j下的最大价值”位置是“前i个物品”约束是“容量j”目标是“最大价值”。把这三个要素想清楚转移方程往往就呼之欲出了。6.2 转移方程的推导套路最后一步分析法路径计数的转移方程是通过“最后一步”推导出来的最后一步要么从上面来要么从左边来。这个“最后一步分析法”是推导动态规划转移方程的通用套路。具体做法是假设你已经到达了最终状态考虑到达这个状态的最后一步有哪些可能。每一种可能对应一个子问题把这些子问题的解合并起来就是原问题的解。合并的方式取决于问题的性质计数问题是相加优化问题是取极值存在性问题是取或。6.3 边界与初始化的通用处理原则边界条件是状态定义在边界上的自然结果不是人为规定的。路径计数中第一行全是1是因为从起点到第一行任意格子只有一条路。这个“只有一条路”是客观事实不是随便设的。初始化时要注意起点值通常为1计数问题或0优化问题表示“什么都不做”的代价。如果起点值设错整个数组都会错。一个检查方法是手动推一个小规模实例看看结果是否符合预期。6.4 从路径计数到其他动态规划问题的迁移路径计数问题教会我们的是“集合划分”的思想。你把所有合法路径按照“最后一步”划分成不相交的子集分别计数再相加。这个思想可以迁移到爬楼梯按照“最后一步走1阶还是2阶”划分零钱兑换按照“最后使用哪种硬币”划分编辑距离按照“最后一个操作是删除、插入还是替换”划分最长公共子序列按照“最后一个字符是否匹配”划分你会发现几乎所有动态规划问题都在做同一件事找到一个划分方式让子问题不相交且覆盖所有情况。路径计数只是这个思想最直观的载体。我在实际做题时遇到不会的动态规划题会先问自己最后一步可能是什么这个问题一旦想清楚转移方程就完成了一半。剩下的就是处理边界和初始化以及考虑是否需要空间优化。最后分享一个我个人的习惯每做完一道动态规划题我会用一个小规模的输入手动推一遍dp表把每个格子的值写出来然后对照代码的输出。这个习惯帮我发现了无数次边界初始化的错误。路径计数问题尤其适合这样做因为它的dp表是二维的可视化程度高推演过程本身就是对状态定义的一次验证。 
长河君 · 2026/10/15 15:52:38 · 阅读 1.2k 从网格路径计数入门动态规划：状态定义、障碍物处理与空间优化
1. 从“爬楼梯”到“网格路径”为什么路径计数是动态规划的最佳练兵场很多人学动态规划第一道题是爬楼梯第二道题是零钱兑换第三道题就卡住了。问题出在哪儿出在爬楼梯太特殊了——它只有一个维度状态转移只跟前面一两个状态有关你甚至可以用两个变量滚动更新连数组都不用开。这种题做多了会产生一种“动态规划不过如此”的错觉等到遇见二维网格、多阶段决策、带障碍物的路径计数立刻被打回原形。路径总数问题恰好卡在“简单”和“复杂”之间。说它简单是因为状态定义几乎写在题面上从起点走到某个格子有多少种走法。说它复杂是因为它强迫你建立二维的状态空间强迫你思考边界条件强迫你处理障碍物带来的状态不可达问题。更关键的是路径计数问题有一个非常直观的几何解释——你走的每一步都在“消耗”一个维度上的剩余步数这种“资源消耗”的视角是理解更复杂动态规划问题的钥匙。我见过太多人做动态规划的方式是“背转移方程”。看到网格就写dp[i][j] dp[i-1][j] dp[i][j-1]看到字符串就写dp[i][j] dp[i-1][j-1] 1。方程背对了题也过了但下次换个场景又不会。根本原因在于他们没有想清楚“状态到底在描述什么”。路径计数问题最大的价值就是逼你把这件事想清楚dp[i][j]不是“走到(i,j)的走法数”这么简单它背后隐含的是“所有从起点到(i,j)的合法路径集合的基数”。这个集合是怎么构成的是由“最后一步从上面来”的路径集合和“最后一步从左边来”的路径集合做并集得到的。因为最后一步不同这两个集合不相交所以总数可以直接相加。这个“集合划分”的思想才是动态规划的精髓。路径计数只是它最朴素的表现形式。你把这个思想吃透了后面做背包问题、编辑距离、最长公共子序列都会有一种“原来都是在做集合划分”的通透感。这篇文章我会从最基础的网格路径计数出发一步步扩展到带障碍物、带权值、多阶段决策的变体重点不是给你一堆代码而是把每一步的“为什么”讲清楚。适合已经写过几道动态规划题但总觉得差点意思的读者也适合想从路径计数这个切口重新理解动态规划的从业者。2. 网格路径计数的状态定义为什么dp[i][j]能表示走法总数2.1 从“走法”到“状态”的抽象过程先看最经典的场景一个m行n列的网格从左上角(0,0)出发每次只能向右或向下走一步问到右下角(m-1,n-1)一共有多少种不同的路径。很多人第一反应是“这题我会”然后直接写代码。但我想先停下来问一个问题为什么可以用一个二维数组来表示“走法总数”走法是一个过程是一个序列怎么用一个数字概括关键在于“无后效性”。当你站在格子(i,j)上时你关心的是“从起点走到这里有多少种走法”而不关心“这些走法具体长什么样”。因为无论你之前怎么走的接下来能走的步骤只取决于你当前的位置——你只能向右或向下跟历史路径无关。这就是无后效性当前状态包含了做出下一步决策所需的全部信息。所以dp[i][j]的定义是从起点(0,0)走到格子(i,j)的所有合法路径的数量。注意这里说的是“数量”不是“路径本身”。我们用一个整数来代表一个集合的基数这是动态规划最核心的压缩思想。2.2 状态转移方程的推导集合的划分与相加有了状态定义接下来推导转移方程。走到(i,j)的最后一步只有两种可能从上面(i-1,j)向下走一步或者从左边(i,j-1)向右走一步。这里有一个容易被忽略的逻辑细节为什么这两种情况的路径数可以直接相加因为“最后一步从上面来”的所有路径和“最后一步从左边来”的所有路径是两个不相交的集合。一条路径不可能最后一步既从上面来又从左边来。既然不相交那么总集合的大小就等于两个子集大小之和。用公式表示就是dp[i][j] dp[i-1][j] dp[i][j-1]这个方程看起来简单但它包含了动态规划的两个基本操作划分和合并。划分是把大问题拆成互不相交的子问题合并是把子问题的解组合成原问题的解。你后面学背包问题划分方式是“选或不选第i个物品”学编辑距离划分方式是“删除、插入、替换”。形式不同本质一样。2.3 边界条件的处理第一行和第一列为什么只有一种走法转移方程里用到了dp[i-1][j]和dp[i][j-1]当i0或j0时会出现越界。所以需要单独处理边界。对于第一行i0你只能一直向右走没有任何其他选择所以dp[0][j] 1。同理第一列j0只能一直向下走dp[i][0] 1。起点dp[0][0] 1表示“站在原地”这一种走法。这里有一个常见的错误把dp[0][0]初始化为0。如果起点是0那么整个数组都会是0因为所有值都是从起点累加出来的。另一个错误是忘记初始化第一行和第一列导致转移方程在边界处取到默认值0结果偏小。注意边界初始化不是“特殊情况”而是状态定义在边界上的自然结果。第一行只有一种走法是因为从(0,0)到(0,j)只有一条水平路径这是客观事实不是人为规定。2.4 从小规模实例手推验证拿一个3x3的网格手动推一遍能帮你建立直觉。网格坐标从(0,0)到(2,2)。第一行全是1dp[0][0]1, dp[0][1]1, dp[0][2]1。 第一列全是1dp[1][0]1, dp[2][0]1。然后逐个填dp[1][1] dp[0][1] dp[1][0] 1 1 2dp[1][2] dp[0][2] dp[1][1] 1 2 3dp[2][1] dp[1][1] dp[2][0] 2 1 3dp[2][2] dp[1][2] dp[2][1] 3 3 6最终答案是6。你可以手动枚举验证从(0,0)到(2,2)需要向右走2步、向下走2步总共4步选择其中2步向下的位置组合数C(4,2)6。结果吻合。这个组合数的视角很重要。当没有障碍物时路径总数就是组合数C(mn-2, m-1)。动态规划的解法本质上是在计算这个组合数只不过用递推的方式避免了阶乘溢出。理解这一点你就能明白为什么动态规划在这个问题上是“用空间换时间”的——它把组合数的计算拆成了一个个小规模的加法。3. 带障碍物的路径计数状态不可达时该怎么处理3.1 障碍物改变了什么从“全部可达”到“部分不可达”基础版的网格路径计数有一个隐含假设所有格子都是可达的。但现实中网格上可能有障碍物比如某些格子不能通过。这时候状态的定义需要微调dp[i][j]表示从起点走到(i,j)且不经过任何障碍物的路径数量。如果(i,j)本身是障碍物那么dp[i][j] 0因为没有任何合法路径能停在一个障碍物上。这个0不是“没有路径”而是“这个状态本身就不合法”。区别在于对于可达的空格子dp值是正数对于障碍物dp值强制为0表示这个状态被“禁用”了。3.2 转移方程在障碍物处的修正转移方程的形式不变仍然是dp[i][j] dp[i-1][j] dp[i][j-1]但前提是(i,j)不是障碍物。如果是障碍物直接跳过保持0。这里有一个容易踩的坑边界初始化。第一行和第一列不再全是1了。如果第一行中间有一个障碍物那么障碍物之后的所有格子都不可达dp值应该是0。因为从起点出发只能向右走一旦遇到障碍物就过不去了。举个例子第一行是[起点, 空格, 障碍, 空格]。dp[0][0]1, dp[0][1]1, dp[0][2]0障碍物dp[0][3]0因为从左边来的路被障碍物堵死了从上面来又不存在。所以边界初始化需要逐个判断如果当前格子是障碍物dp0否则如果是最左边或最上面dp等于前一个格子的dp值。3.3 一个具体的障碍物网格推演假设3x3网格障碍物在(1,1)。坐标从(0,0)到(2,2)。初始化dp[0][0]1, dp[0][1]1, dp[0][2]1第一行无障碍dp[1][0]1, dp[2][0]1第一列无障碍填表dp[1][1]是障碍物dp0dp[1][2] dp[0][2] dp[1][1] 1 0 1dp[2][1] dp[1][1] dp[2][0] 0 1 1dp[2][2] dp[1][2] dp[2][1] 1 1 2答案是2。手动验证从(0,0)到(2,2)必须经过(1,1)吗不一定。路径可以是(0,0)-(0,1)-(0,2)-(1,2)-(2,2)或者(0,0)-(1,0)-(2,0)-(2,1)-(2,2)。这两条路都绕开了(1,1)。其他路径都会经过(1,1)所以只有2条。结果正确。3.4 障碍物问题的实操心得在实际写代码时我习惯把障碍物格子的dp值在初始化阶段就设为0然后在填表循环里加一个判断如果当前格子是障碍物直接continue。这样代码逻辑清晰不容易出错。另一个经验是不要试图在转移方程里处理障碍物。有些人会写成dp[i][j] (isObstacle[i][j] ? 0 : dp[i-1][j] dp[i][j-1])这样写没问题但可读性差。更好的做法是把障碍物的判断提前让转移方程保持最简形式。还有一个边界情况如果起点或终点本身就是障碍物直接返回0。这个判断要放在最前面否则后面的初始化逻辑会变得很别扭。4. 路径计数的空间优化从二维数组到一维滚动4.1 为什么可以压缩空间状态依赖的方向性标准的二维dp需要O(m*n)的空间。但观察转移方程dp[i][j] dp[i-1][j] dp[i][j-1]你会发现计算第i行时只依赖第i-1行的数据和当前行左边的数据。也就是说第i-2行及更早的数据在计算完第i-1行后就不再需要了。这意味着我们可以用一个一维数组来滚动更新。具体做法是维护一个长度为n的数组dpdp[j]在更新前代表上一行i-1行第j列的值更新后代表当前行i行第j列的值。更新顺序必须是从左到右。因为dp[j] dp[j]上一行的值 dp[j-1]当前行已更新的值。如果从右到左更新dp[j-1]还是上一行的值就错了。4.2 一维数组的初始化和更新细节初始化dp[0] 1起点其余dp[j] 1第一行只有一种走法。如果有障碍物遇到障碍物时dp[j] 0并且后续的dp值要相应调整。更新过程用代码表示for i in range(m): for j in range(n): if obstacle[i][j]: dp[j] 0 elif j 0: dp[j] dp[j] dp[j-1] # j 0 时dp[0]保持不变第一列只有一种走法注意j 0的情况dp[0]在每一行都应该是1如果没有障碍物因为它代表第一列只能一直向下走。但在有障碍物的情况下如果第一列某个格子是障碍物dp[0]要变成0并且后续行的dp[0]也保持0。4.3 空间优化的收益与代价空间从O(m*n)降到O(n)当n很大时收益明显。但代价是代码可读性下降调试难度增加。我的建议是如果是面试或竞赛先写二维版本确保逻辑正确再考虑优化。如果是生产环境空间优化带来的性能提升通常不值得牺牲可维护性除非m和n确实非常大。还有一个细节如果m n可以交换行列让一维数组的长度取较小值进一步节省空间。这个技巧在矩阵很大的时候有用但要注意交换后障碍物的坐标也要相应转置。5. 路径计数的变体带权值、多阶段与组合数学视角5.1 带权值的最小路径和从计数到优化路径计数是“有多少种走法”带权值的最小路径和是“哪种走法代价最小”。状态定义从“数量”变成“最小值”转移方程从“相加”变成“取最小再加当前权值”。dp[i][j] min(dp[i-1][j], dp[i][j-1]) grid[i][j]这个变体看起来只是把加法换成min但它代表了一类重要的动态规划问题最优化问题。计数问题是“求和”优化问题是“求极值”。两者的共同点是都需要划分状态空间区别在于合并方式不同。在实际操作中带权值问题的边界初始化要注意第一行和第一列不再是1而是累加值。dp[0][j] dp[0][j-1] grid[0][j]因为只有一条路可走代价就是沿途权值之和。5.2 多阶段决策每一步有多个选择的情况如果网格中每个格子可以向多个方向走比如四个方向问题就变成了图上的路径计数。这时候动态规划可能不再适用因为状态之间可能存在环不满足无后效性。你需要用记忆化搜索或者拓扑排序来处理。但如果方向仍然是向右和向下只是每一步可以选择走1步或2步那么状态转移方程会变成dp[i][j] dp[i-1][j] dp[i-2][j] dp[i][j-1] dp[i][j-2]这本质上是在更大的步长上做划分。理解了这个你就能明白为什么动态规划的转移方程可以灵活调整——只要你能保证子问题不相交且覆盖所有情况。5.3 组合数学视角什么时候不需要动态规划当没有障碍物时路径总数就是组合数C(mn-2, m-1)。这个公式的推导很简单总共需要走mn-2步其中m-1步向下n-1步向右选择哪些步向下即可。那为什么还要用动态规划因为组合数计算涉及大数阶乘容易溢出而且当有障碍物时组合数公式不再适用。动态规划的优势在于它天然处理障碍物和权值而且递推过程中数字增长是渐进的不容易溢出当然如果路径数太大仍然需要取模。在实际工程中如果确认没有障碍物且m、n不大直接用组合数公式更快。但如果有任何不确定性动态规划是更稳妥的选择。6. 动态规划解题思路的通用框架从路径计数中提炼6.1 状态定义的三个要素位置、约束、目标路径计数问题的状态定义包含三个要素位置(i,j)、约束只能向右或向下、目标到达终点的路径数。推广到一般动态规划问题状态定义需要明确当前处于哪个阶段位置有哪些限制条件约束需要优化或计算什么目标。很多动态规划题难就难在状态定义。比如背包问题状态是“前i个物品在容量j下的最大价值”位置是“前i个物品”约束是“容量j”目标是“最大价值”。把这三个要素想清楚转移方程往往就呼之欲出了。6.2 转移方程的推导套路最后一步分析法路径计数的转移方程是通过“最后一步”推导出来的最后一步要么从上面来要么从左边来。这个“最后一步分析法”是推导动态规划转移方程的通用套路。具体做法是假设你已经到达了最终状态考虑到达这个状态的最后一步有哪些可能。每一种可能对应一个子问题把这些子问题的解合并起来就是原问题的解。合并的方式取决于问题的性质计数问题是相加优化问题是取极值存在性问题是取或。6.3 边界与初始化的通用处理原则边界条件是状态定义在边界上的自然结果不是人为规定的。路径计数中第一行全是1是因为从起点到第一行任意格子只有一条路。这个“只有一条路”是客观事实不是随便设的。初始化时要注意起点值通常为1计数问题或0优化问题表示“什么都不做”的代价。如果起点值设错整个数组都会错。一个检查方法是手动推一个小规模实例看看结果是否符合预期。6.4 从路径计数到其他动态规划问题的迁移路径计数问题教会我们的是“集合划分”的思想。你把所有合法路径按照“最后一步”划分成不相交的子集分别计数再相加。这个思想可以迁移到爬楼梯按照“最后一步走1阶还是2阶”划分零钱兑换按照“最后使用哪种硬币”划分编辑距离按照“最后一个操作是删除、插入还是替换”划分最长公共子序列按照“最后一个字符是否匹配”划分你会发现几乎所有动态规划问题都在做同一件事找到一个划分方式让子问题不相交且覆盖所有情况。路径计数只是这个思想最直观的载体。我在实际做题时遇到不会的动态规划题会先问自己最后一步可能是什么这个问题一旦想清楚转移方程就完成了一半。剩下的就是处理边界和初始化以及考虑是否需要空间优化。最后分享一个我个人的习惯每做完一道动态规划题我会用一个小规模的输入手动推一遍dp表把每个格子的值写出来然后对照代码的输出。这个习惯帮我发现了无数次边界初始化的错误。路径计数问题尤其适合这样做因为它的dp表是二维的可视化程度高推演过程本身就是对状态定义的一次验证。