1. 项目概述从棋盘到代码的路径计数“不同路径问题”是算法学习尤其是动态规划入门时绕不开的一道经典题目。我第一次接触它感觉就像在玩一个简化版的棋盘游戏一个机器人位于一个m x n网格的左上角每次只能向下或者向右移动一步问它到达右下角总共有多少条不同的路径这个问题看似简单却蕴含着动态规划最核心的“状态定义”与“状态转移”思想。后来题目升级网格中加入了障碍物通常用1表示障碍0表示空地问题就变成了“不同路径 II”难度和实用性都提升了一个档次。在力扣LeetCode上这正是第62题和第63题。为什么我们要用 C 来解决它因为 C 给了我们一个绝佳的舞台来亲手操控内存、观察状态数组的每一个变化从而深刻理解动态规划“表格填充”的本质。相比于一些高级语言封装好的便利用 C 实现能让你看清算法每一步的“成本”——时间复杂度和空间复杂度是如何被计算和优化的。无论是准备面试时被问到的“如何优化空间复杂度到 O(n) 甚至 O(1)”还是在实际项目中处理类似的网格寻路、概率计算问题这个基础都至关重要。接下来我会带你从最朴素的思路开始一步步推导并用 C 实现同时分享我在调试和优化过程中踩过的坑和总结的技巧。2. 问题拆解与核心思路分析2.1 问题定义与抽象建模我们先明确两个版本的问题不同路径无障碍给定m和n表示网格的行数和列数。机器人从(0, 0)出发到达(m-1, n-1)。求所有可能的、不回溯的路径数量。不同路径 II有障碍在m x n网格的基础上额外给出一个二维数组obstacleGrid其中obstacleGrid[i][j]为1则表示该位置有障碍物不可通过为0则表示空地。同样求从左上角到右下角的路径数当终点或起点有障碍时路径数为0。如何抽象我们可以把网格的每一个格子(i, j)看作一个“状态”这个状态的值dp[i][j]就表示“从起点(0, 0)走到(i, j)这个位置有多少种不同的走法”。这就是动态规划中最关键的步骤定义状态数组。那么如何求出dp[i][j]呢考虑机器人最后一步是怎么走到(i, j)的。由于它只能向下或向右走那么它只可能从正上方的格子(i-1, j)向下走一步过来或者从左边的格子(i, j-1)向右走一步过来。因此到达(i, j)的路径数就等于到达(i-1, j)的路径数加上到达(i, j-1)的路径数。这就是我们的状态转移方程dp[i][j] dp[i-1][j] dp[i][j-1]。对于有障碍的情况逻辑需要修正如果(i, j)本身就是障碍物那么dp[i][j]直接为0因为不可能站在障碍物上。在计算状态转移时如果来源格子是障碍物那么其对应的路径数贡献为0。2.2 动态规划思路的逐步推导理解了这个核心我们来看看如何初始化这个“表格”。起点(0, 0)是我们的出发点到达起点的路径数显然是1一种方式不动。再看第一行(0, j)机器人要走到这些位置只能一路向右无法从上方来因为上方没有格子所以第一行所有格子的路径数都是1前提是路径上没有障碍。同理第一列(i, 0)的所有格子路径数也都是1因为只能一路向下。有了初始状态第一行和第一列和状态转移方程我们就可以像填表格一样从左到右、从上到下地计算出每一个dp[i][j]的值最终dp[m-1][n-1]就是我们想要的答案。这个过程的时间复杂度是O(m*n)因为我们需要遍历并计算网格中的每一个格子。空间复杂度也是O(m*n)因为我们开辟了一个同样大小的二维数组来存储状态。注意这里有一个初学者极易混淆的点。状态dp[i][j]表示的是“走到这个格子的路径数”而不是“经过这个格子的路径数”。前者是累计值后者可能需要更复杂的图论思想。我们当前解决的是前者也是面试中最常考的形式。3. C实现与逐行代码解析理论清晰后我们动手实现。我会先给出无障碍版本的完整代码并附上详细注释然后再讨论有障碍版本的改动。3.1 基础版本无障碍网格的实现#include iostream #include vector using namespace std; class Solution { public: int uniquePaths(int m, int n) { // 1. 创建并初始化dp表大小为 m x n所有值先设为0 vectorvectorint dp(m, vectorint(n, 0)); // 2. 初始化第一行和第一列 for (int i 0; i m; i) { dp[i][0] 1; // 第一列只能从上往下走只有1条路径 } for (int j 0; j n; j) { dp[0][j] 1; // 第一行只能从左往右走只有1条路径 } // 3. 状态转移填充dp表的其余部分 for (int i 1; i m; i) { for (int j 1; j n; j) { // 到达(i,j)的路径数 从上边来的路径数 从左边来的路径数 dp[i][j] dp[i - 1][j] dp[i][j - 1]; } } // 4. 返回终点的路径数 return dp[m - 1][n - 1]; } }; int main() { Solution sol; int m 3, n 7; // 示例3行7列的网格 int result sol.uniquePaths(m, n); cout 在 m x n 的网格中不同路径数为: result endl; // 输出在 3x7 的网格中不同路径数为: 28 return 0; }代码解析与实操心得使用vectorvectorint这是C中表示动态二维数组最方便和安全的方式。vectorint(n, 0)创建了一个包含n个0的向量vectorvectorint dp(m, ...)则创建了m个这样的向量构成了m x n的矩阵。这比手动用new分配内存要安全得多无需担心内存泄漏。初始化的重要性单独处理第一行和第一列是必须的因为我们的状态转移方程dp[i][j] dp[i-1][j] dp[i][j-1]在i0或j0时会越界。这种“边界条件初始化”是动态规划代码的常见模式。循环顺序填充dp表时我们使用了双层循环外层i从1到m-1内层j从1到n-1。这个顺序是固定的必须确保在计算dp[i][j]时dp[i-1][j]上方和dp[i][j-1]左方都已经被计算出来。从左到右、从上到下的顺序正好满足这个要求。3.2 升级版本处理有障碍的网格有障碍物的版本核心逻辑不变但初始化状态转移时都需要考虑障碍物。#include iostream #include vector using namespace std; class Solution { public: int uniquePathsWithObstacles(vectorvectorint obstacleGrid) { int m obstacleGrid.size(); if (m 0) return 0; int n obstacleGrid[0].size(); if (n 0) return 0; // 如果起点或终点就是障碍物直接返回0 if (obstacleGrid[0][0] 1 || obstacleGrid[m - 1][n - 1] 1) { return 0; } // 创建dp表 vectorvectorint dp(m, vectorint(n, 0)); // 初始化起点 dp[0][0] 1; // 初始化第一列如果当前格子是障碍物则路径数为0并且后续格子也无法到达路径数保持为0 for (int i 1; i m; i) { if (obstacleGrid[i][0] 1) { dp[i][0] 0; // 这里可以加一个break因为一旦遇到障碍下面的格子肯定也到不了 // 但为了逻辑清晰我们继续循环dp值会保持为初始值0 } else { dp[i][0] dp[i - 1][0]; // 只能从上方来 } } // 初始化第一行逻辑同上 for (int j 1; j n; j) { if (obstacleGrid[0][j] 1) { dp[0][j] 0; } else { dp[0][j] dp[0][j - 1]; // 只能从左方来 } } // 状态转移 for (int i 1; i m; i) { for (int j 1; j n; j) { if (obstacleGrid[i][j] 1) { dp[i][j] 0; // 当前是障碍物不可达 } else { dp[i][j] dp[i - 1][j] dp[i][j - 1]; } } } return dp[m - 1][n - 1]; } }; int main() { Solution sol; vectorvectorint obstacleGrid { {0, 0, 0}, {0, 1, 0}, {0, 0, 0} }; int result sol.uniquePathsWithObstacles(obstacleGrid); cout 在有障碍物的网格中不同路径数为: result endl; // 输出在有障碍物的网格中不同路径数为: 2 return 0; }有障碍版本的实现要点提前判断起点和终点这是一个有效的剪枝操作。如果起点或终点本身就是障碍答案必然是0可以直接返回避免无谓的计算。初始化逻辑的变化初始化第一行和第一列时不能简单地全部赋值为1。如果当前格子(i, 0)是障碍那么dp[i][0] 0。如果不是障碍那么它的值取决于它上一个格子(i-1, 0)的值因为只能从上方来即dp[i][0] dp[i-1][0]。第一行同理。这意味着如果在第一行或第一列中遇到一个障碍物那么这个障碍物之后的所有格子其dp值都将是0因为路径被阻断了。状态转移中的判断在双重循环中对于每个格子(i, j)首先判断它是不是障碍物。如果是dp[i][j]直接为0。如果不是才执行dp[i][j] dp[i-1][j] dp[i][j-1]。这里的dp[i-1][j]和dp[i][j-1]如果对应的是障碍物格子它们的值已经是0所以加法运算自然就排除了从障碍物方向来的路径。4. 空间复杂度优化技巧上面我们用的都是O(m*n)的空间这在m和n很大时可能成为瓶颈。仔细观察状态转移方程dp[i][j] dp[i-1][j] dp[i][j-1]你会发现在计算第i行时我们只需要用到**上一行第i-1行的数据以及当前行已经计算过的左边部分第j-1列**的数据。因此我们完全不需要保存整个m x n的表格只需要保存两行当前行和上一行甚至一行就够了。4.1 滚动数组优化O(n)空间我们可以只用一个一维数组dp来解决问题其长度为列数n。在计算过程中这个一维数组在每一行被重复利用滚动。在计算第i行时dp[j]在更新前存储的其实是上一行第j列的值即dp[i-1][j]。当我们从左到右计算dp[j]的新值时dp[j-1]已经被更新为当前行第j-1列的值即dp[i][j-1]而dp[j]还未被覆盖仍然是上一行第j列的值即dp[i-1][j]。因此状态转移方程可以写为dp[j] dp[j] dp[j-1]。等号右边的dp[j]是旧值来自上一行dp[j-1]是新值当前行已计算。等号左边的dp[j]是更新后的当前行值。无障碍版本的滚动数组实现int uniquePaths(int m, int n) { vectorint dp(n, 1); // 初始化相当于第一行的路径数都是1 for (int i 1; i m; i) { // 从第二行开始计算 for (int j 1; j n; j) { dp[j] dp[j] dp[j - 1]; } // 注意第一列j0的dp[0]始终为1因为每一行的第一个格子只能从上方来。 // 在我们的循环中j从1开始所以dp[0]的值在整个过程中保持不变初始化为1。 } return dp[n - 1]; }有障碍版本的滚动数组实现更复杂一些int uniquePathsWithObstacles(vectorvectorint obstacleGrid) { int m obstacleGrid.size(), n obstacleGrid[0].size(); if (obstacleGrid[0][0] 1) return 0; vectorint dp(n, 0); dp[0] 1; // 起点 // 初始化第一行在滚动数组中 for (int j 1; j n; j) { dp[j] (obstacleGrid[0][j] 0) ? dp[j - 1] : 0; } // 计算后续行 for (int i 1; i m; i) { // 更新当前行的第一列 dp[0] (obstacleGrid[i][0] 0) ? dp[0] : 0; for (int j 1; j n; j) { if (obstacleGrid[i][j] 1) { dp[j] 0; } else { dp[j] dp[j] dp[j - 1]; } } } return dp[n - 1]; }实操心得滚动数组优化是面试中的高频考点。理解的关键在于想清楚一维数组dp在每一轮循环中扮演的双重角色它既存储了上一行的结果又在被逐步覆盖为当前行的结果。写代码时要特别注意对第一行和第一列的特殊处理在滚动数组模式下如何体现。对于有障碍物的情况逻辑会稍显复杂建议先在纸上模拟一个小网格如3x3的计算过程跟踪dp数组的变化理解透彻后再写代码。4.2 进一步优化到O(1)空间原地修改如果题目允许修改输入的obstacleGrid矩阵我们甚至可以不使用额外的dp数组而是直接复用obstacleGrid来存储路径数当然需要把障碍物标记从1改为0把空地0用于存储路径数。其思想和滚动数组完全一致只是把dp数组搬到了原矩阵上。这种做法将空间复杂度降到了O(1)。但在实际面试或工程中修改输入参数通常不被鼓励除非题目明确说明可以。这里了解思路即可。5. 调试技巧与边界条件处理动态规划的代码看似简洁但边界条件极易出错。以下是我在调试中总结的几个检查点网格尺寸为0这是LeetCode等平台常见的边界测试。如果m 0或n 0应该直接返回0因为不存在有效的网格。我们的代码在开头就应该加上这个判断。起点/终点即障碍对于“不同路径 II”必须在开始计算前检查obstacleGrid[0][0]和obstacleGrid[m-1][n-1]。如果它们是障碍物无论中间有多少路结果都是0。大数溢出路径数可能是一个非常大的数字例如m100, n100时结果是一个巨大的组合数。题目通常要求返回int但实际值可能超出int范围。在C中这可能导致溢出得到负数或错误结果。如果题目有此顾虑可以使用long long甚至unsigned long long来定义dp数组或者在每次加法后进行取模操作如果题目要求返回结果对某个数取模。在实际编写时要留意题目描述中的数据范围提示。初始化陷阱在基础版本中初始化第一行第一列为1是没问题的。但在有障碍版本中如果第一行中间有个障碍物那么这个障碍物右边的所有格子都应该初始化为0而不是1。我们的代码通过判断obstacleGrid[i][j]并依赖前一个状态dp[i-1][0]或dp[0][j-1]来正确实现了这一点。务必用包含障碍物在第一行或第一列的测试用例来验证你的初始化逻辑。6. 从算法到应用思维延伸解决了标准问题后我们可以思考一些变种这有助于深化理解变种1带有权值的网格。每个格子有一个权值代表通过成本求从左上角到右下角的最小路径和。这依然是动态规划状态dp[i][j]变为“到达(i, j)的最小路径和”转移方程为dp[i][j] min(dp[i-1][j], dp[i][j-1]) grid[i][j]。变种2输出所有路径。此时动态规划只计数就不够了需要用回溯DFS来遍历所有可能的路径并记录下来。时间复杂度会指数级增长。变种3方向扩展。如果机器人可以向上、下、左、右四个方向移动但不能重复访问格子求路径数。这就变成了一个图论中的路径计数问题在网格较大时可能需要用更高级的算法或数学方法。我个人在实际编码中的一个体会是动态规划类问题画图是最有效的调试和理解工具。在纸上画一个小的网格手动填充dp表观察每一个数字是如何由它左边和上边的数字得来的。这个过程能让你直观地理解状态转移也能迅速发现初始化或转移逻辑中的错误。对于滚动数组优化在纸上模拟一维数组在每一行计算前后的变化是理解其工作原理的不二法门。不要急于写代码先把状态定义、转移方程和边界条件在草稿上理清楚代码实现就是水到渠成的事情了。