1. 项目概述从迷宫到最优路径如果你写过一些基础的C/C程序比如计算斐波那契数列可能会发现递归虽然直观但计算fib(40)时电脑就开始“思考人生”了。这种重复计算的低效正是动态规划Dynamic Programming, DP要解决的核心问题。而路径问题是理解动态规划思想最经典、最直观的战场。它不像一些纯数学的DP那样抽象你可以非常具象地看到一个“决策者”在网格中一步步走向终点每一步的选择都影响着最终结果。这次我们要实战解决的正是这样一个问题在一个m x n的网格中每次只能向右或向下移动一个格子从左上角(0, 0)出发到达右下角(m-1, n-1)一共有多少种不同的路径这个问题看似简单却是打开DP世界大门的钥匙。它不要求你具备高深的图论知识只需要基础的编程能力和一点对“状态”的敏感度。通过解决它你将掌握DP最核心的“状态定义”、“状态转移方程”和“空间优化”三板斧这些思想能直接迁移到股票买卖、字符串编辑距离等更复杂的问题上。无论你是正在准备算法面试的学生还是希望提升代码效率的开发者这个从暴力递归到优化DP的完整思考与实现过程都值得你亲手敲一遍代码来体会。2. 核心思路拆解为什么是动态规划面对“多少种路径”这个问题我们的第一反应可能是搜索从起点开始尝试所有向右和向下的组合直到终点然后计数。这本质上是深度优先搜索DFS。写出来大概是这样int dfs(int i, int j, int m, int n) { if (i m || j n) return 0; // 出界无效路径 if (i m - 1 j n - 1) return 1; // 到达终点找到一条路径 return dfs(i 1, j, m, n) dfs(i, j 1, m, n); // 向下走 向右走 }调用dfs(0, 0, m, n)就能得到答案。但是当m和n都为20时你会发现程序慢得难以忍受。因为DFS遍历了所有可能的路径其时间复杂度是指数级的O(2^(mn))其中存在大量的重复计算。例如从(0,0)到(1,1)无论你是先右后下还是先下后右最终都会在计算(1,1)这个位置出发的路径数时被重复计算。注意这里就是动态规划出现的典型场景——问题具有“重叠子问题”和“最优子结构”。重叠子问题指在求解过程中相同的子问题被反复计算最优子结构指一个问题的最优解包含其子问题的最优解。我们的路径总数问题“到达(i,j)的路径数”就是一个子问题它的解可以从(i-1,j)和(i,j-1)这两个子问题的解推导出来。因此动态规划的思路应运而生我们不再重复计算子问题而是把每个子问题的答案存起来用的时候直接查表。具体到本题状态定义我们定义dp[i][j]为从起点(0, 0)走到格子(i, j)的路径数量。我们最终想要的就是dp[m-1][n-1]。状态转移方程如何计算dp[i][j]由于只能向右或向下走所以要走到(i, j)上一步只可能是从(i-1, j)向下走一步或者从(i, j-1)向右走一步。因此到达(i, j)的路径数就是到达这两个相邻格子路径数的总和。方程如下dp[i][j] dp[i-1][j] dp[i][j-1]初始化最上面一行(i0)和最左边一列(j0)怎么算因为只能向右或向下所以沿着网格的上边线从起点一直向右走只有1种走法同样沿着左边线一直向下走也只有1种走法。因此我们需要初始化dp[0][j] 1对所有j以及dp[i][0] 1对所有i。这个思路将指数级复杂度的搜索问题转化为了一个需要填充m x n表格的O(m*n)时间复杂度的计算问题效率提升是巨大的。2.1 从二维DP到一维优化空间的取舍艺术上面我们定义了一个二维数组dp[m][n]。但在实际计算时如果你观察状态转移方程dp[i][j] dp[i-1][j] dp[i][j-1]会发现计算第i行的数据时只依赖于第i-1行和当前行已计算过的第j-1列的数据。这意味着我们并不需要保存整个二维历史只需要保存“上一行”的数据就足够了。我们可以将二维DP压缩成一维数组dp[n]其中n是列数。在一维表示下dp[j]在更新前存储的其实是二维场景中dp[i-1][j]的值即上一行同列的值。dp[j-1]在更新时存储的已经是二维场景中dp[i][j-1]的值即当前行左边一列刚更新完的值。 因此状态转移可以在一维数组内原地进行dp[j] dp[j] dp[j-1]。等号右边的dp[j]是“旧值”代表来自上方的路径数dp[j-1]是“新值”代表来自左方的路径数。这种优化将空间复杂度从O(m*n)降到了O(n)。在面试或竞赛中主动提出并实现空间优化能很好地体现你对算法理解的深度。当然在初次理解时使用二维DP思路更清晰优化则是锦上添花。3. 完整代码实现与逐行解析下面我将给出从基础二维DP到一维空间优化的完整C代码并附上详细的注释。我们假设网格的行数m和列数n由用户输入。3.1 基础二维动态规划版本这个版本最直观最适合理解DP表格的填充过程。#include iostream #include vector using namespace std; int uniquePaths_2d(int m, int n) { // 1. 创建二维dp表大小为 m x n并初始化为0 vectorvectorint dp(m, vectorint(n, 0)); // 2. 初始化边界条件 // 第一行的所有格子只能从起点一直向右走到达路径数为1 for (int j 0; j n; j) { dp[0][j] 1; } // 第一列的所有格子只能从起点一直向下走到达路径数为1 for (int i 0; i m; i) { dp[i][0] 1; } // 3. 状态转移按行优先顺序填充dp表 // 注意i和j从1开始因为第0行和第0列已经初始化了 for (int i 1; i m; i) { for (int j 1; j n; j) { // 核心转移方程当前格子的路径数 上方格子路径数 左方格子路径数 dp[i][j] dp[i - 1][j] dp[i][j - 1]; } } // 4. 返回终点格子的结果 return dp[m - 1][n - 1]; } int main() { int m, n; cout 请输入网格的行数m和列数n (以空格分隔): ; cin m n; int paths uniquePaths_2d(m, n); cout 从(0,0)到( m-1 , n-1 )的不同路径总数为: paths endl; // 可选打印dp表帮助理解 // cout DP表内容如下 endl; // vectorvectorint dp(m, vectorint(n, 0)); // ... (初始化并填充dp表然后打印) return 0; }代码要点解析使用vectorvectorint来构建二维数组比原生数组更安全方便自动管理内存。初始化两步不能合并到双重循环里因为逻辑不同边界是固定的1内部格子需要计算。填充顺序必须是“行优先”或者“列优先”确保在计算dp[i][j]时dp[i-1][j]和dp[i][j-1]都已经计算好了。这是DP的“无后效性”要求。3.2 优化的一维动态规划版本这个版本在功能上与二维版本完全一致但更节省内存。#include iostream #include vector using namespace std; int uniquePaths_1d(int m, int n) { // 1. 创建一维dp数组大小为n列数并初始化为1 // 初始化dp[j]1代表了二维表中第一行dp[0][j]的初始值 vectorint dp(n, 1); // 2. 状态转移 // 外层循环i从1到m-1代表计算第1行到最后一行 for (int i 1; i m; i) { // 内层循环j从1到n-1代表计算当前行第1列到最后一列 // 注意j必须从左向右遍历因为dp[j]依赖于更新后的dp[j-1]左方 for (int j 1; j n; j) { // 核心转移dp[j]新 dp[j]旧代表上方 dp[j-1]新代表左方 dp[j] dp[j] dp[j-1]; // 上式等价于dp[j] dp[j-1]; } // 当每一行计算完成后dp数组存储的就是当前行所有格子的路径数 // 进入下一轮循环(i1)时dp数组自然就变成了“上一行”的数据 } // 3. 返回结果dp数组的最后一个元素dp[n-1]就是终点格子的路径数 return dp[n - 1]; } int main() { int m, n; cout 请输入网格的行数m和列数n (以空格分隔): ; cin m n; int paths uniquePaths_1d(m, n); cout 从(0,0)到( m-1 , n-1 )的不同路径总数为: paths endl; return 0; }代码要点与易错点初始化vectorint dp(n, 1)巧妙地同时完成了两个任务一是将一维数组所有元素置1这对应了二维表中第一行dp[0][j]1二是在后续计算中dp[0]的值始终为1这对应了每一行的第一列dp[i][0]1。你可以验证当j0时内层循环for (int j1; ...)不会执行所以dp[0]在整个过程中保持为1不变。遍历顺序内层循环j必须从左向右遍历。因为dp[j]依赖于本轮已经更新过的dp[j-1]代表来自左边的路径。如果从右向左遍历使用的dp[j-1]就是上一行的旧值逻辑就错了。空间理解最难理解的是dp[j] dp[j] dp[j-1];这一行。等号右边的dp[j]在未被覆盖前存储的是i-1行j列的值来自上方等号右边的dp[j-1]在当前j的循环中已经被更新为i行j-1列的值来自左方。两者相加就得到了i行j列的新值。实操心得一维DP的写法非常简洁但容易在遍历顺序上犯错。一个很好的调试方法是用一个小例子比如3x3网格手动模拟一下二维DP表和一维数组在每一步的变化写在纸上瞬间就能理解其精妙之处。这也是面试官喜欢考察的点。4. 算法扩展与变种问题思考掌握了基础模型很多变种问题都可以迎刃而解。这里分享几个常见的变种和解题思路你可以尝试自己编码实现。4.1 变种一网格中存在障碍物这是LeetCode上经典的“不同路径 II”问题。网格中某些格子有障碍物用1表示机器人不能通过。求路径数。思路调整初始化如果起点或终点有障碍物直接返回0。初始化第一行和第一列时一旦遇到障碍物后面的格子都到达不了路径数为0因为只能向右或向下走。状态转移在计算dp[i][j]时先判断(i, j)是否是障碍物。如果是则dp[i][j] 0否则依然执行dp[i][j] dp[i-1][j] dp[i][j-1]。一维优化依然适用但在更新dp[j]前需要判断当前位置是否为障碍物。如果是需要将dp[j]显式设置为0因为一维数组中可能还保留着上一行的值。核心代码片段一维DPint uniquePathsWithObstacles(vectorvectorint obstacleGrid) { int m obstacleGrid.size(), n obstacleGrid[0].size(); if (obstacleGrid[0][0] 1 || obstacleGrid[m-1][n-1] 1) return 0; vectorint dp(n, 0); dp[0] 1; // 起点 for (int i 0; i m; i) { for (int j 0; j n; j) { if (obstacleGrid[i][j] 1) { dp[j] 0; // 当前位置是障碍路径数为0 } else if (j 0) { // 状态转移dp[j]来自上方dp[j-1]来自左方 dp[j] dp[j] dp[j-1]; } // 当j0时dp[0]的值由上一轮循环和本轮的障碍判断决定 } } return dp[n-1]; }4.2 变种二最小路径和同样是m x n网格每个格子有一个非负整数代表经过该格子的“代价”。求从左上角到右下角的路径使得路径上的数字总和最小。思路转变状态定义dp[i][j]变为从起点(0,0)走到(i,j)的最小路径和。状态转移到达(i,j)的最小和等于到达其上方或左方格子的最小和加上(i,j)自身的值。即dp[i][j] min(dp[i-1][j], dp[i][j-1]) grid[i][j]。初始化dp[0][0] grid[0][0]。第一行只能从左来dp[0][j] dp[0][j-1] grid[0][j]。第一列只能从上来dp[i][0] dp[i-1][0] grid[i][0]。一维优化同样适用转移方程为dp[j] min(dp[j], dp[j-1]) grid[i][j]。这个变种将DP从“计数问题”推广到了“优化问题”是DP应用的另一个重要方向。4.3 变种三路径问题的数学解法对于没有障碍物的基础路径问题其实有一个组合数学的公式从(0,0)走到(m-1, n-1)总共需要移动(m-1)(n-1) mn-2步其中向下m-1步向右n-1步。不同的路径本质上就是这mn-2步中选择m-1个位置向下走或者选择n-1个位置向右走的组合数。因此总路径数为C(mn-2, m-1)或C(mn-2, n-1)。C实现注意溢出long long uniquePaths_math(int m, int n) { // 计算 C(N, k)其中 N mn-2, k min(m-1, n-1) 以减少计算量 long long N m n - 2; long long k min(m - 1, n - 1); long long result 1; // 利用组合数公式 C(N, k) N! / (k! * (N-k)!) // 展开计算为 result (N * (N-1) * ... * (N-k1)) / (1 * 2 * ... * k) for (long long i 1; i k; i) { result result * (N - k i) / i; // 边乘边除避免过早溢出 } return result; }注意事项虽然数学解法在时间复杂度O(min(m,n))和空间复杂度O(1)上都是最优的但必须小心处理大数的阶乘和除法使用long long类型并采用“边乘边除”的策略是防止中间结果溢出的关键。在面试中先给出DP解法再提一下数学解作为补充会显得思维非常全面。5. 调试技巧与常见问题排查即使理解了算法第一次实现时也难免遇到问题。下面是我在学习和教学过程中总结的几个常见“坑点”及解决方法。5.1 数组越界访问这是C/C程序员永远的痛。在DP问题中尤其容易发生在边界处理上。问题场景在双重循环中i和j从1开始但访问了dp[i-1][j]或dp[i][j-1]。如果i或j的循环范围设置错误比如i从0开始就会访问dp[-1][j]导致越界。排查方法仔细检查循环的起始和终止条件。记住我们通常将第0行和第0列单独初始化因此内部格子的计算从(1,1)开始。使用vector的at()方法如dp.at(i).at(j)可以在越界时抛出异常帮助定位问题虽然性能略有损耗但调试时很实用。5.2 初始化错误初始化是DP正确性的基石。问题场景对于基础路径问题错误地将整个dp数组初始化为1或者只初始化了dp[0][0]1而忘了第一行和第一列的其他格子。排查方法用最小的例子测试比如m1, n1只有起点路径应为1m1, n5只有一行路径应为1m5, n1只有一列路径应为1。这些边界案例能快速检验初始化逻辑。5.3 一维DP遍历顺序错误这是空间优化版本的特有错误。问题场景在内层循环中j从n-1递减到0从右向左遍历。这会导致dp[j]在计算时dp[j-1]还是上一行的旧值而不是当前行已更新的值计算结果错误。排查方法同样使用小网格如2x2, 3x3进行手动演算或打印每步的dp数组。你会发现从左向右遍历时dp数组的更新是符合二维表行优先填充顺序的。5.4 整数溢出路径数可能增长得非常快。问题场景当m和n较大时比如都是10路径数会是一个很大的数。如果使用int类型可能会溢出导致负数或错误结果。排查方法根据问题规模预估结果大小。对于mn10路径数是C(18,9)48620还在int范围内。但当mn20时路径数是C(38,19)35345263800远超32位int的范围。在竞赛或面试中如果没有明确说明使用long long64位整数是更安全的选择。我们的示例代码为了清晰使用了int在实际应用中需要留意。5.5 调试信息打印对于DP问题最有效的调试手段之一就是打印出整个DP表。void printDPTable(const vectorvectorint dp) { for (const auto row : dp) { for (int val : row) { cout val \t; } cout endl; } }在状态转移循环结束后调用这个函数将计算出的dp表打印出来。你可以立刻与手动计算的结果进行比对任何错误都无所遁形。对于一维DP可以在每行计算结束后打印当前的dp数组观察其如何从“上一行”演变为“当前行”。6. 性能分析与实战选择我们来对比一下讨论过的几种方法的性能以便你在不同场景下做出选择。方法时间复杂度空间复杂度优点缺点适用场景暴力DFSO(2^(mn))O(mn) (递归栈深度)思路直观代码简单效率极低无法处理稍大规模数据仅用于理解问题无实用价值二维DPO(m*n)O(m*n)思路清晰易于理解和调试空间占用较大教学、理解、网格较小或对空间不敏感时一维DPO(m*n)O(n)空间效率高代码简洁理解难度稍高边界和遍历顺序易错面试、竞赛、处理大规模网格的首选组合数学O(min(m, n))O(1)时间和空间都是最优涉及大数计算可能溢出不通用仅限无障碍基础问题已知是无障碍网格且对性能要求极高时实战选择建议面试中首选实现一维DP。在解释时可以先从二维DP的思路讲起定义状态、转移方程、初始化然后自然地引出空间优化。这展示了你的思维层次从解决问题到优化问题。竞赛中如果问题是最基础的无障碍路径计数且m和n很大直接使用组合数学解法但要处理好溢出。对于变种问题有障碍、求最小和等一维DP是通用且可靠的武器。日常开发与学习从二维DP开始编写和调试确保完全理解。然后尝试改写成二维DP并用手动模拟来加深理解。最后可以尝试实现变种问题巩固举一反三的能力。动态规划路径问题就像算法世界里的一个经典训练场它体积小、结构清晰但五脏俱全涵盖了状态、转移、优化等核心概念。把它吃透再去看背包问题、子序列问题你会发现很多思路都是相通的。我个人的体会是学习算法不能只停留在看懂一定要动手把代码敲出来用不同的测试用例去跑甚至故意写错几个地方看看会发生什么这个过程中获得的“手感”和深刻理解是只看书和文章永远无法替代的。最后一个小技巧在面试中如果被问到DP问题可以先从最简单的暴力递归开始分析然后指出其重叠子问题再引出记忆化搜索自顶向下DP最后优化成迭代法自底向上DP乃至空间优化版本这一套完整的思考链路比直接背出最优解代码更能赢得面试官的青睐。
1. 项目概述从迷宫到最优路径如果你写过一些基础的C/C程序比如计算斐波那契数列可能会发现递归虽然直观但计算fib(40)时电脑就开始“思考人生”了。这种重复计算的低效正是动态规划Dynamic Programming, DP要解决的核心问题。而路径问题是理解动态规划思想最经典、最直观的战场。它不像一些纯数学的DP那样抽象你可以非常具象地看到一个“决策者”在网格中一步步走向终点每一步的选择都影响着最终结果。这次我们要实战解决的正是这样一个问题在一个m x n的网格中每次只能向右或向下移动一个格子从左上角(0, 0)出发到达右下角(m-1, n-1)一共有多少种不同的路径这个问题看似简单却是打开DP世界大门的钥匙。它不要求你具备高深的图论知识只需要基础的编程能力和一点对“状态”的敏感度。通过解决它你将掌握DP最核心的“状态定义”、“状态转移方程”和“空间优化”三板斧这些思想能直接迁移到股票买卖、字符串编辑距离等更复杂的问题上。无论你是正在准备算法面试的学生还是希望提升代码效率的开发者这个从暴力递归到优化DP的完整思考与实现过程都值得你亲手敲一遍代码来体会。2. 核心思路拆解为什么是动态规划面对“多少种路径”这个问题我们的第一反应可能是搜索从起点开始尝试所有向右和向下的组合直到终点然后计数。这本质上是深度优先搜索DFS。写出来大概是这样int dfs(int i, int j, int m, int n) { if (i m || j n) return 0; // 出界无效路径 if (i m - 1 j n - 1) return 1; // 到达终点找到一条路径 return dfs(i 1, j, m, n) dfs(i, j 1, m, n); // 向下走 向右走 }调用dfs(0, 0, m, n)就能得到答案。但是当m和n都为20时你会发现程序慢得难以忍受。因为DFS遍历了所有可能的路径其时间复杂度是指数级的O(2^(mn))其中存在大量的重复计算。例如从(0,0)到(1,1)无论你是先右后下还是先下后右最终都会在计算(1,1)这个位置出发的路径数时被重复计算。注意这里就是动态规划出现的典型场景——问题具有“重叠子问题”和“最优子结构”。重叠子问题指在求解过程中相同的子问题被反复计算最优子结构指一个问题的最优解包含其子问题的最优解。我们的路径总数问题“到达(i,j)的路径数”就是一个子问题它的解可以从(i-1,j)和(i,j-1)这两个子问题的解推导出来。因此动态规划的思路应运而生我们不再重复计算子问题而是把每个子问题的答案存起来用的时候直接查表。具体到本题状态定义我们定义dp[i][j]为从起点(0, 0)走到格子(i, j)的路径数量。我们最终想要的就是dp[m-1][n-1]。状态转移方程如何计算dp[i][j]由于只能向右或向下走所以要走到(i, j)上一步只可能是从(i-1, j)向下走一步或者从(i, j-1)向右走一步。因此到达(i, j)的路径数就是到达这两个相邻格子路径数的总和。方程如下dp[i][j] dp[i-1][j] dp[i][j-1]初始化最上面一行(i0)和最左边一列(j0)怎么算因为只能向右或向下所以沿着网格的上边线从起点一直向右走只有1种走法同样沿着左边线一直向下走也只有1种走法。因此我们需要初始化dp[0][j] 1对所有j以及dp[i][0] 1对所有i。这个思路将指数级复杂度的搜索问题转化为了一个需要填充m x n表格的O(m*n)时间复杂度的计算问题效率提升是巨大的。2.1 从二维DP到一维优化空间的取舍艺术上面我们定义了一个二维数组dp[m][n]。但在实际计算时如果你观察状态转移方程dp[i][j] dp[i-1][j] dp[i][j-1]会发现计算第i行的数据时只依赖于第i-1行和当前行已计算过的第j-1列的数据。这意味着我们并不需要保存整个二维历史只需要保存“上一行”的数据就足够了。我们可以将二维DP压缩成一维数组dp[n]其中n是列数。在一维表示下dp[j]在更新前存储的其实是二维场景中dp[i-1][j]的值即上一行同列的值。dp[j-1]在更新时存储的已经是二维场景中dp[i][j-1]的值即当前行左边一列刚更新完的值。 因此状态转移可以在一维数组内原地进行dp[j] dp[j] dp[j-1]。等号右边的dp[j]是“旧值”代表来自上方的路径数dp[j-1]是“新值”代表来自左方的路径数。这种优化将空间复杂度从O(m*n)降到了O(n)。在面试或竞赛中主动提出并实现空间优化能很好地体现你对算法理解的深度。当然在初次理解时使用二维DP思路更清晰优化则是锦上添花。3. 完整代码实现与逐行解析下面我将给出从基础二维DP到一维空间优化的完整C代码并附上详细的注释。我们假设网格的行数m和列数n由用户输入。3.1 基础二维动态规划版本这个版本最直观最适合理解DP表格的填充过程。#include iostream #include vector using namespace std; int uniquePaths_2d(int m, int n) { // 1. 创建二维dp表大小为 m x n并初始化为0 vectorvectorint dp(m, vectorint(n, 0)); // 2. 初始化边界条件 // 第一行的所有格子只能从起点一直向右走到达路径数为1 for (int j 0; j n; j) { dp[0][j] 1; } // 第一列的所有格子只能从起点一直向下走到达路径数为1 for (int i 0; i m; i) { dp[i][0] 1; } // 3. 状态转移按行优先顺序填充dp表 // 注意i和j从1开始因为第0行和第0列已经初始化了 for (int i 1; i m; i) { for (int j 1; j n; j) { // 核心转移方程当前格子的路径数 上方格子路径数 左方格子路径数 dp[i][j] dp[i - 1][j] dp[i][j - 1]; } } // 4. 返回终点格子的结果 return dp[m - 1][n - 1]; } int main() { int m, n; cout 请输入网格的行数m和列数n (以空格分隔): ; cin m n; int paths uniquePaths_2d(m, n); cout 从(0,0)到( m-1 , n-1 )的不同路径总数为: paths endl; // 可选打印dp表帮助理解 // cout DP表内容如下 endl; // vectorvectorint dp(m, vectorint(n, 0)); // ... (初始化并填充dp表然后打印) return 0; }代码要点解析使用vectorvectorint来构建二维数组比原生数组更安全方便自动管理内存。初始化两步不能合并到双重循环里因为逻辑不同边界是固定的1内部格子需要计算。填充顺序必须是“行优先”或者“列优先”确保在计算dp[i][j]时dp[i-1][j]和dp[i][j-1]都已经计算好了。这是DP的“无后效性”要求。3.2 优化的一维动态规划版本这个版本在功能上与二维版本完全一致但更节省内存。#include iostream #include vector using namespace std; int uniquePaths_1d(int m, int n) { // 1. 创建一维dp数组大小为n列数并初始化为1 // 初始化dp[j]1代表了二维表中第一行dp[0][j]的初始值 vectorint dp(n, 1); // 2. 状态转移 // 外层循环i从1到m-1代表计算第1行到最后一行 for (int i 1; i m; i) { // 内层循环j从1到n-1代表计算当前行第1列到最后一列 // 注意j必须从左向右遍历因为dp[j]依赖于更新后的dp[j-1]左方 for (int j 1; j n; j) { // 核心转移dp[j]新 dp[j]旧代表上方 dp[j-1]新代表左方 dp[j] dp[j] dp[j-1]; // 上式等价于dp[j] dp[j-1]; } // 当每一行计算完成后dp数组存储的就是当前行所有格子的路径数 // 进入下一轮循环(i1)时dp数组自然就变成了“上一行”的数据 } // 3. 返回结果dp数组的最后一个元素dp[n-1]就是终点格子的路径数 return dp[n - 1]; } int main() { int m, n; cout 请输入网格的行数m和列数n (以空格分隔): ; cin m n; int paths uniquePaths_1d(m, n); cout 从(0,0)到( m-1 , n-1 )的不同路径总数为: paths endl; return 0; }代码要点与易错点初始化vectorint dp(n, 1)巧妙地同时完成了两个任务一是将一维数组所有元素置1这对应了二维表中第一行dp[0][j]1二是在后续计算中dp[0]的值始终为1这对应了每一行的第一列dp[i][0]1。你可以验证当j0时内层循环for (int j1; ...)不会执行所以dp[0]在整个过程中保持为1不变。遍历顺序内层循环j必须从左向右遍历。因为dp[j]依赖于本轮已经更新过的dp[j-1]代表来自左边的路径。如果从右向左遍历使用的dp[j-1]就是上一行的旧值逻辑就错了。空间理解最难理解的是dp[j] dp[j] dp[j-1];这一行。等号右边的dp[j]在未被覆盖前存储的是i-1行j列的值来自上方等号右边的dp[j-1]在当前j的循环中已经被更新为i行j-1列的值来自左方。两者相加就得到了i行j列的新值。实操心得一维DP的写法非常简洁但容易在遍历顺序上犯错。一个很好的调试方法是用一个小例子比如3x3网格手动模拟一下二维DP表和一维数组在每一步的变化写在纸上瞬间就能理解其精妙之处。这也是面试官喜欢考察的点。4. 算法扩展与变种问题思考掌握了基础模型很多变种问题都可以迎刃而解。这里分享几个常见的变种和解题思路你可以尝试自己编码实现。4.1 变种一网格中存在障碍物这是LeetCode上经典的“不同路径 II”问题。网格中某些格子有障碍物用1表示机器人不能通过。求路径数。思路调整初始化如果起点或终点有障碍物直接返回0。初始化第一行和第一列时一旦遇到障碍物后面的格子都到达不了路径数为0因为只能向右或向下走。状态转移在计算dp[i][j]时先判断(i, j)是否是障碍物。如果是则dp[i][j] 0否则依然执行dp[i][j] dp[i-1][j] dp[i][j-1]。一维优化依然适用但在更新dp[j]前需要判断当前位置是否为障碍物。如果是需要将dp[j]显式设置为0因为一维数组中可能还保留着上一行的值。核心代码片段一维DPint uniquePathsWithObstacles(vectorvectorint obstacleGrid) { int m obstacleGrid.size(), n obstacleGrid[0].size(); if (obstacleGrid[0][0] 1 || obstacleGrid[m-1][n-1] 1) return 0; vectorint dp(n, 0); dp[0] 1; // 起点 for (int i 0; i m; i) { for (int j 0; j n; j) { if (obstacleGrid[i][j] 1) { dp[j] 0; // 当前位置是障碍路径数为0 } else if (j 0) { // 状态转移dp[j]来自上方dp[j-1]来自左方 dp[j] dp[j] dp[j-1]; } // 当j0时dp[0]的值由上一轮循环和本轮的障碍判断决定 } } return dp[n-1]; }4.2 变种二最小路径和同样是m x n网格每个格子有一个非负整数代表经过该格子的“代价”。求从左上角到右下角的路径使得路径上的数字总和最小。思路转变状态定义dp[i][j]变为从起点(0,0)走到(i,j)的最小路径和。状态转移到达(i,j)的最小和等于到达其上方或左方格子的最小和加上(i,j)自身的值。即dp[i][j] min(dp[i-1][j], dp[i][j-1]) grid[i][j]。初始化dp[0][0] grid[0][0]。第一行只能从左来dp[0][j] dp[0][j-1] grid[0][j]。第一列只能从上来dp[i][0] dp[i-1][0] grid[i][0]。一维优化同样适用转移方程为dp[j] min(dp[j], dp[j-1]) grid[i][j]。这个变种将DP从“计数问题”推广到了“优化问题”是DP应用的另一个重要方向。4.3 变种三路径问题的数学解法对于没有障碍物的基础路径问题其实有一个组合数学的公式从(0,0)走到(m-1, n-1)总共需要移动(m-1)(n-1) mn-2步其中向下m-1步向右n-1步。不同的路径本质上就是这mn-2步中选择m-1个位置向下走或者选择n-1个位置向右走的组合数。因此总路径数为C(mn-2, m-1)或C(mn-2, n-1)。C实现注意溢出long long uniquePaths_math(int m, int n) { // 计算 C(N, k)其中 N mn-2, k min(m-1, n-1) 以减少计算量 long long N m n - 2; long long k min(m - 1, n - 1); long long result 1; // 利用组合数公式 C(N, k) N! / (k! * (N-k)!) // 展开计算为 result (N * (N-1) * ... * (N-k1)) / (1 * 2 * ... * k) for (long long i 1; i k; i) { result result * (N - k i) / i; // 边乘边除避免过早溢出 } return result; }注意事项虽然数学解法在时间复杂度O(min(m,n))和空间复杂度O(1)上都是最优的但必须小心处理大数的阶乘和除法使用long long类型并采用“边乘边除”的策略是防止中间结果溢出的关键。在面试中先给出DP解法再提一下数学解作为补充会显得思维非常全面。5. 调试技巧与常见问题排查即使理解了算法第一次实现时也难免遇到问题。下面是我在学习和教学过程中总结的几个常见“坑点”及解决方法。5.1 数组越界访问这是C/C程序员永远的痛。在DP问题中尤其容易发生在边界处理上。问题场景在双重循环中i和j从1开始但访问了dp[i-1][j]或dp[i][j-1]。如果i或j的循环范围设置错误比如i从0开始就会访问dp[-1][j]导致越界。排查方法仔细检查循环的起始和终止条件。记住我们通常将第0行和第0列单独初始化因此内部格子的计算从(1,1)开始。使用vector的at()方法如dp.at(i).at(j)可以在越界时抛出异常帮助定位问题虽然性能略有损耗但调试时很实用。5.2 初始化错误初始化是DP正确性的基石。问题场景对于基础路径问题错误地将整个dp数组初始化为1或者只初始化了dp[0][0]1而忘了第一行和第一列的其他格子。排查方法用最小的例子测试比如m1, n1只有起点路径应为1m1, n5只有一行路径应为1m5, n1只有一列路径应为1。这些边界案例能快速检验初始化逻辑。5.3 一维DP遍历顺序错误这是空间优化版本的特有错误。问题场景在内层循环中j从n-1递减到0从右向左遍历。这会导致dp[j]在计算时dp[j-1]还是上一行的旧值而不是当前行已更新的值计算结果错误。排查方法同样使用小网格如2x2, 3x3进行手动演算或打印每步的dp数组。你会发现从左向右遍历时dp数组的更新是符合二维表行优先填充顺序的。5.4 整数溢出路径数可能增长得非常快。问题场景当m和n较大时比如都是10路径数会是一个很大的数。如果使用int类型可能会溢出导致负数或错误结果。排查方法根据问题规模预估结果大小。对于mn10路径数是C(18,9)48620还在int范围内。但当mn20时路径数是C(38,19)35345263800远超32位int的范围。在竞赛或面试中如果没有明确说明使用long long64位整数是更安全的选择。我们的示例代码为了清晰使用了int在实际应用中需要留意。5.5 调试信息打印对于DP问题最有效的调试手段之一就是打印出整个DP表。void printDPTable(const vectorvectorint dp) { for (const auto row : dp) { for (int val : row) { cout val \t; } cout endl; } }在状态转移循环结束后调用这个函数将计算出的dp表打印出来。你可以立刻与手动计算的结果进行比对任何错误都无所遁形。对于一维DP可以在每行计算结束后打印当前的dp数组观察其如何从“上一行”演变为“当前行”。6. 性能分析与实战选择我们来对比一下讨论过的几种方法的性能以便你在不同场景下做出选择。方法时间复杂度空间复杂度优点缺点适用场景暴力DFSO(2^(mn))O(mn) (递归栈深度)思路直观代码简单效率极低无法处理稍大规模数据仅用于理解问题无实用价值二维DPO(m*n)O(m*n)思路清晰易于理解和调试空间占用较大教学、理解、网格较小或对空间不敏感时一维DPO(m*n)O(n)空间效率高代码简洁理解难度稍高边界和遍历顺序易错面试、竞赛、处理大规模网格的首选组合数学O(min(m, n))O(1)时间和空间都是最优涉及大数计算可能溢出不通用仅限无障碍基础问题已知是无障碍网格且对性能要求极高时实战选择建议面试中首选实现一维DP。在解释时可以先从二维DP的思路讲起定义状态、转移方程、初始化然后自然地引出空间优化。这展示了你的思维层次从解决问题到优化问题。竞赛中如果问题是最基础的无障碍路径计数且m和n很大直接使用组合数学解法但要处理好溢出。对于变种问题有障碍、求最小和等一维DP是通用且可靠的武器。日常开发与学习从二维DP开始编写和调试确保完全理解。然后尝试改写成二维DP并用手动模拟来加深理解。最后可以尝试实现变种问题巩固举一反三的能力。动态规划路径问题就像算法世界里的一个经典训练场它体积小、结构清晰但五脏俱全涵盖了状态、转移、优化等核心概念。把它吃透再去看背包问题、子序列问题你会发现很多思路都是相通的。我个人的体会是学习算法不能只停留在看懂一定要动手把代码敲出来用不同的测试用例去跑甚至故意写错几个地方看看会发生什么这个过程中获得的“手感”和深刻理解是只看书和文章永远无法替代的。最后一个小技巧在面试中如果被问到DP问题可以先从最简单的暴力递归开始分析然后指出其重叠子问题再引出记忆化搜索自顶向下DP最后优化成迭代法自底向上DP乃至空间优化版本这一套完整的思考链路比直接背出最优解代码更能赢得面试官的青睐。
