本文共 2380 字，大约阅读时间需要 7 分钟。

机器人网格路径计数问题

在一个M×N网格中，有一个机器人从左上角的“Start”位置移动到右下角的“Finish”位置。机器人每次只能向下或向右移动一步。我们需要计算有多少条不同的路径。

问题分析

这个问题属于经典的组合数学问题，可以通过动态规划（DP）来解决。动态规划是一种高效的算法方法，能够将大型问题分解为更小的子问题，从而逐步求解。

动态规划方法

我们使用一个二维数组 dp 来存储每个位置的路径数。dp[i][j] 表示从左上角到位置 (i, j) 的路径数。

代码实现

int uniquePaths(int m, int n) {    vector
   
     dp(n, 1);    for (int i = 1; i < m; ++i) {        for (int j = 1; j < n; ++j) {            dp[j] += dp[j - 1];        }    }    return dp.back();}
   

代码解读

• 初始化一个一维数组 dp，长度为 n，所有元素初始化为 1。
• 遍历每个位置：
  • 对于每一行 i，从左到右遍历每一列 j：
    • 更新 dp[j] 为 dp[j] + dp[j-1]，即左边位置的路径数加上上边位置的路径数。
• 最终返回路径数 dp.back()。

样例计算

以 3×7 网格为例：

• 数组大小为 7，初始化为 [1,1,1,1,1,1,1]
• 第 1 行：无法移动，保持不变。
• 第 2 行到第 3 行，逐步计算：
  • dp[j] = dp[j] + dp[j-1]
• 最终得到路径数 70。

扩展问题：存在障碍物的情况

为了进一步验证，我们引入障碍物，将网格中的某些位置标记为无法通过。

问题描述

给定一个 M×N 的网格，网格中包含障碍物和空位。障碍物用 1 表示，空位用 0 表示。计算从起点到终点的路径数，排除经过障碍物的路径。

解决方法

• 动态规划数组 dp：同样用于存储当前位置的路径数。
• 双重检查障碍物：
  • 如果当前位置或左上位置有障碍物，则从左边或上边来到当前位置的路径数为 0。
  • 如果左边或上边位置是否有障碍物，决定是否需要遍历后面的位置。

递推公式调整

if (obstacleGrid[i-1][j] == 1 || obstacleGrid[i][j-1] == 1) {    dp[i][j] = 0;} else {    dp[i][j] = (dp[i-1][j] + dp[i][j-1]);}

样例案例

考虑一个 3×3 网格：

[\begin{bmatrix}0 & 0 & 0 \0 & 1 & 0 \0 & 0 & 0\end{bmatrix}]

代码输出 2，即存在两条有效路径。

代码实现

int uniquePathsWithObstacles(vector
   
    
     > obstacleGrid) {    int m = obstacleGrid.size();    int n = obstacleGrid[0].size();    vector
     
       dp(m, vector
      
       (n, 0));    dp[0][0] = 1;    for (int i = 0; i < m; ++i) {        for (int j = 0; j < n; ++j) {            if (i == 0 && j == 0) continue;            if (obstacleGrid[i][j] == 1) {                dp[i][j] = 0;                continue;            }            int ways = 0;            if (i > 0 && obstacleGrid[i-1][j] != 1 && dp[i-1][j] > 0) {                ways += dp[i-1][j];            }            if (j > 0 && obstacleGrid[i][j-1] != 1 && dp[i][j-1] > 0) {                ways += dp[i][j-1];            }            dp[i][j] = ways;        }    }    return dp.back().back();}
      
     
    
   

代码解读

• 初始化 dp 数组，起点为 1。
• 遍历每个位置：
  • 如果当前位置是障碍物，路径数为 0。
  • 否则，从上边和左边引来的路径数之和即为当前位置的路径数。
• 最终返回 dp[m-1][n-1] 即终点位置的路径数。

总结

通过上述方法，我们可以在 O(MN) 时间复杂度内解决问题。动态规划是一种强大的工具，能够帮助我们解决路径计数问题，扩展性良好，可以轻松处理有障碍物的情况。

如果将网格尺寸进一步扩大，可以考虑使用 memoization 或递归方法，以优化代码的可读性。

转载地址：http://dywfk.baihongyu.com/