不同路径Ⅰ

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。问总共有多少条不同的路径？

例如，下图是一个7 x 3 的网格。有多少可能的路径？
不同的路径问题 - 图1

示例 1:

  1. 输入: m = 3, n = 2
  2. 输出: 3
  3. 解释:
  4. 从左上角开始，总共有 3 条路径可以到达右下角。
  5. 1. 向右 -> 向右 -> 向下
  6. 2. 向右 -> 向下 -> 向右
  7. 3. 向下 -> 向右 -> 向右

示例 2:

  1. 输入: m = 7, n = 3
  2. 输出: 28

提示：

  • 1 <= m, n <= 100
  • 题目数据保证答案小于等于 2 * 10 ^ 9

题目给定一个二维的网格图，🤖从左上角[0, 0]位置出发，最终要到达右下角的[m, n]处，需要找到有多少条路径能够完成这样的过程。如果更泛化一点讲，给定起点位置为[i, j]，目的位置为[p, q]，找所有可能的路径的数量。因此，我们可以从全局缩小到某一个局部来思考，到达位置[i, j]的路径有多少。如下所示：
image.png

由于题目规定了只能向下或者向右移动一步，因此，能够到达[i, j]位置处的可能是[i, j-1]向右走了一步，也可能是[i-1, j]向下走了一步。总之，[i, j]的状态依赖于[i, j-1]和[i-1, j]，如果知道了[i, j-1]和[i-1, j]位置处对应的路径数量，那么到达[i, j]处的路径数量就这两者数量之和。根据状态转移的关系，显然该题可以使用动态规划来解。

假设dp数组dp[i][j]表示到达[i, j]位置处的路径数量，那么需要考虑两种情况：

  • 对于边界的网格来说，即第一行或者第一列的网格来说，可能的路径只能是向右和向下，因此：不同的路径问题 - 图3
  • 对于其他位置来说，动态转移方程为：不同的路径问题 - 图4

遍历所有的网格，就可以获取到到达任意一处的路径数量。

  1. class Solution{
  2.     public int uniquePaths(int m, int n) {
  3.         int[][] dp = new int[m][n];
  5.         for(int i = 0; i < m; i++){
  6.             for(int j = 0; j < n; j++){
  7.                 if(i == 0 || j == 0){
  8.                     dp[i][j] = 1;
  9.                 } else {
  10.                     dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
  11.             }
  12.         }
  14.         return dp[m - 1][n - 1];
  15.     }
  16. }

不同路径 II

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
不同的路径问题 - 图5
网格中的障碍物和空位置分别用 1 和 0 来表示。

示例 1：
**不同的路径问题 - 图6

  1. 输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
  2. 输出：2
  3. 解释：
  4. 3x3 网格的正中间有一个障碍物。
  5. 从左上角到右下角一共有 2 条不同的路径：
  6. 1. 向右 -> 向右 -> 向下 -> 向下
  7. 2. 向下 -> 向下 -> 向右 -> 向右

示例 2：
不同的路径问题 - 图7

  1. 输入：obstacleGrid = [[0,1],[0,0]]
  2. 输出：1

提示：

  • m == obstacleGrid.length
  • n == obstacleGrid[i].length
  • 1 <= m, n <= 100
  • obstacleGrid[i][j] 为 0 或 1

该题相比于前一题来说，整体的过程是相同的，不同之处在于网络的路径上可能有障碍物。那么，对于除了边界之外的某一个位置[i, j]来说，可能的情况有：

  • 左边的格子有障碍物，如下所示：

image.png
那么对应的动态转移方程是：不同的路径问题 - 图9

  • 上边的格子有障碍物，如下所示：

image.png
对应的动态转移方程为：不同的路径问题 - 图11

  • 左边和上边都是障碍物，如下所示：

image.png
那么，没有路径可以达到[i, j]处，因此不同的路径问题 - 图13。

经过上述可以分析，对于位置[i, j]来说，只要该处没有障碍物，那么动态转移方程不同的路径问题 - 图14仍然成立。

解题代码如下：

  1. class Solution {
  2.     public int uniquePathsWithObstacles(int[][] obstacleGrid) {
  3.         int m = obstacleGrid.length;
  4.         int n = obstacleGrid[0].length;
  5.         int[][] dp = new int[m][n];
  7.         for(int i = 0; i < m && obstacleGrid[i][0] == 0; i++){
  8.             dp[i][0] = 1;
  9.         }
  11.         for(int j = 0; j < n && obstacleGrid[0][j] == 0; j++){
  12.             dp[0][j] = 1;
  13.         }
  15.         for(int i = 1; i < m; i++){
  16.             for(int j = 1; j < n; j++){
  17.                 if(obstacleGrid[i][j] == 0){
  18.                     dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
  19.                 }
  20.             }
  21.         }
  23.         return dp[m - 1][n - 1];
  24.     }
  25. }

或者直接在两次for循环中考虑第一列、第一行和其他的情况：

  1. class Solution {
  2.     public int uniquePathsWithObstacles(int[][] obstacleGrid) {
  3.        int m = obstacleGrid.length;
  4.         int n = obstacleGrid[0].length;
  5.         int[][] dp = new int[m][n];
  7.         // row_f：行标识位，只要前面有一个格子有障碍物，值就变为true
  8.         // row_c：列标识位，只要前面有一个格子有障碍物，值就变为true
  9.         boolean row_f = false, col_f = false;
  10.         for(int i = 0; i < m; i++) {
  11.             for (int j = 0; j < n; j++) {
  12.                 if (i == 0 && col_f == false) {
  13.                     if (obstacleGrid[0][j] == 0) {
  14.                         dp[0][j] = 1;
  15.                     } else {
  16.                         dp[0][j] = 0;
  17.                         col_f = true;
  18.                     }
  19.                 }
  21.                 if (j == 0 && row_f == false) {
  22.                     if (obstacleGrid[i][0] == 0) {
  23.                         dp[i][0] = 1;
  24.                     } else {
  25.                         dp[i][0] = 0;
  26.                         row_f = true;
  27.                     }
  28.                 }
  30.                 // 只考虑格子中没有障碍物的情况
  31.                 if(i != 0 && j != 0 && obstacleGrid[i][j] == 0){
  32.                     dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
  33.                 }
  34.             }
  35.         }
  36.         return dp[m - 1][n - 1];
  37.     }
  38. }

不同的路径Ⅲ

在二维网格 grid 上，有 4 种类型的方格：

  • 1 表示起始方格。且只有一个起始方格。
  • 2 表示结束方格，且只有一个结束方格。
  • 0 表示我们可以走过的空方格。
  • -1 表示我们无法跨越的障碍。

返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目。每一个无障碍方格都要通过一次，但是一条路径中不能重复通过同一个方格。

示例 1：

  1. 输入：[[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
  2. 输出：2
  3. 解释：我们有以下两条路径：
  4. 1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
  5. 2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)

示例 2：

  1. 输入：[[1,0,0,0],[0,0,0,0],[0,0,0,2]]
  2. 输出：4
  3. 解释：我们有以下四条路径：
  4. 1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
  5. 2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
  6. 3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
  7. 4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)

示例 3：

  1. 输入：[[0,1],[2,0]]
  2. 输出：0
  3. 解释：
  4. 没有一条路能完全穿过每一个空的方格一次。
  5. 请注意，起始和结束方格可以位于网格中的任意位置。

提示：

  • 1 <= grid.length * grid[0].length <= 20

该题和上面两题又有所不同，出发点和终点不再是固定的左上角和右下角，而是类型为1的为出发点，类型为2的为终点。并且要求通过所有无障碍的方格，对应的类型为0。允许上下左右四个方向的行走，最后统计不同路径的数目。由于题目要求寻找所有可能的路径，因此使用深搜+回溯的方法来解。

经过上面的分析可知，在深搜之前需要完成几件事：

  • 寻找出发点的坐标，即标识为1的点
  • 统计无障碍方格的数目，后续判断路径是否合法时使用

找到了出发点和知道了无障碍方格的数目后，便可以开始通过深搜➕回溯来寻找可能的路径。对于走到的具体方格位置[x, y]来说：

  • 如果位置越界或者此方格标识为-1，则表示非法路径，直接返回0
  • 如果当前方格表示为2，表示已经到达终点，判断是否走完了所有的无障碍方格
  • 否则，继续走，走的方向有上下左右四种

解题代码如下：

  1. class Solution {
  2.     public int uniquePathsIII(int[][] grid) {
  3.         // 起始点坐标
  4.         int sx = 0, sy = 0;
  5.         // 无障碍方格数
  6.         int steps = 1;
  7.         for (int i = 0; i < grid.length; i++){
  8.             for (int j = 0; j < grid[0].length; j++){
  9.                 if (grid[i][j] == 1){
  10.                     sx = i;
  11.                     sy = j;
  12.                     continue;
  13.                 }
  14.                 if (grid[i][j] == 0) 
  15.                     steps++;
  16.             }
  17.         }
  18.         return dfs(sx, sy, steps, grid);
  19.     }
  21.     // 深搜寻找所有可能路径
  22.     public int dfs(int x, int y, int steps, int[][] grid){
  23.         // 如果位置越界或者碰到障碍点，直接返回0，此路不通
  24.         if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == -1) 
  25.             return 0;    
  27.         // 到达终点
  28.         if (grid[x][y] == 2) 
  29.             // 走完所有的无障碍点，表示和一条合法的路径；否则非法
  30.             return steps == 0 ? 1 : 0;
  32.         // 记录状态信息，凡走过的方格不能再走
  33.         grid[x][y] = -1;  
  34.         // 统计合法路径数量
  35.         int count = 0;
  36.         count += dfs(x - 1, y, steps - 1, grid) + dfs(x + 1, y, steps - 1, grid) + dfs(x, y - 1, steps - 1, grid) + dfs(x, y + 1, steps - 1, grid);
  37.            // 撤销状态
  38.         grid[x][y] = 0; 
  40.         return count;
  41.     }
  42. }