社区首页 >专栏 >不同路径问题

不同路径问题

你的益达

发布于 2020-08-05 07:34:58

1.1K00

代码可运行

文章被收录于专栏：阿伟的个人博客阿伟的个人博客

运行总次数：0

代码可运行

不同路径II

问题描述：

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

网格中的障碍物和空位置分别用 1 和 0 来表示。

示例 1:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-paths-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

dfs + 回溯

定义dfs(i, j) 返回从i, j出发到达终点的路径条数。

由于其只能往右和往下，dfs(i, j) = dfs(i + 1, j) + dfs(i, j +1)

递归终止

i ,j为终点时返回1。

实现代码如下：

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if(obstacleGrid.length == 0){
            return 0;
        }
        int M = obstacleGrid.length;
        int N = obstacleGrid[0].length;
        boolean[][] access = new boolean[M][N];
        return dfs(0, 0, obstacleGrid, access);
    }
    public int dfs(int x, int y, int[][] grid, boolean[][] access){
        if(x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || access[x][y] || grid[x][y] == 1){
            return 0;
        }
        if(x == grid.length - 1 && y == grid[0].length - 1){
            return 1;
        }
        access[x][y] = true;
        int ans = 0;
        ans = dfs(x + 1, y, grid, access) + dfs(x, y + 1, grid, access);
        access[x][y] = false;
        return ans;
    }
}

超时了，很显然这问题得改为dp。

动态规划

定义dp[i] [j]为从i , j位置出发到达终点的路径数目。

转移方程：

dp[i][j] = \begin{cases}dp[i + 1][j]+dp[i][j+1] \qquad grid[i][j] = 0\\\ 0 \qquad\qquad\qquad\qquad\qquad\qquad grid[i][j] = 1\end{cases}

baseline:

dp[M-1][N-1] =\begin{cases}1 \qquad grid[i][j] = 0\\\ 0 \qquad grid[i][j] = 1\end{cases}

dp[M-1][j] =\begin{cases}1 \qquad grid[M - 1][j] = 0,dp[M - 1][j] = 1\\\ 0 \qquad else\end{cases}\qquad\\\dp[i][N - 1] =\begin{cases}1 \qquad grid[i][N - 1] = 0,dp[i][N-1] = 1\\\ 0 \qquad else\end{cases}\qquad

上式中M为网络的行数，N为网络的列数，

i \in [0, M - 2],j \in[0,N-2]

实现代码如下：

class Solution {
    public int uniquePathsWithObstacles(int[][] grid) {
        if(grid.length == 0){
            return 0;
        }
        int M = grid.length;
        int N = grid[0].length;
        if(grid[M - 1][N - 1] == 1){
            return 0;
        }
        int[][] dp = new int[M][N];
        dp[M - 1][N - 1] = 1;
        for(int i = M - 2; i >= 0; i--){
            if(grid[i][N - 1] == 0){
                dp[i][N - 1] = 1;
            }else{
                break;
            }
        }
        for(int j = N - 2; j >= 0; j--){
            if(grid[M - 1][j] == 0){
                dp[M - 1][j] = 1;
            }else{
                break;
            }
        }
        for(int i = M - 2; i >= 0; i--){
            for(int j = N - 2; j >= 0; j--){
                if(grid[i][j] == 1){
                    continue;
                }
                dp[i][j] = dp[i + 1][j] + dp[i][j + 1];
            }
        }
        return dp[0][0];
    }
}

不同路径I

问题描述：

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？

示例 1:

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

输入: m = 7, n = 3
输出: 28


提示：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-paths
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解决方案

该问题是之前问题的简化版，解法相同，直接给出转移方程和baseline。

转移方程：

dp[i][j] = dp[i + 1][j]+dp[i][j+1]

baseline:

dp[M - 1][j] = 1\\\dp[i][N - 1] = 1\\\其中i \in [0, M - 1],j \in[0,N-1]

实现代码如下：

class Solution {
    public int uniquePaths(int m, int n) {// C(n + m - 2, n - 1)
        int[][] dp = new int[m][n];
        for(int i = m - 1; i >= 0; i--){
            dp[i][n - 1] = 1;
        }
        for(int j = n - 1; j >= 0; j--){
            dp[m - 1][j] = 1;
        }
        for(int i = m - 2; i >= 0; i--){
            for(int j = n - 2; j >= 0; j--){
                dp[i][j] = dp[i + 1][j] + dp[i][j + 1];
            }
        }
        return dp[0][0];
    }
}

不同路径III

问题描述：

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

1 表示起始方格。且只有一个起始方格。 2 表示结束方格，且只有一个结束方格。 0 表示我们可以走过的空方格。 -1 表示我们无法跨越的障碍。返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目，每一个无障碍方格都要通过一次。

示例 1：

输入：[[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
输出：2
解释：我们有以下两条路径：
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
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,0,0,0],[0,0,0,0],[0,0,0,2]]
输出：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)
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)
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)
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：

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

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-paths-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解决方案

该问题与之前问题相比不光存在障碍点，方向也变为上下左右四个方向，并且还需要每条路径走过所有的无障碍方格。发现数据范围在20以内，决定使用回溯+dfs求解。

我们使用一整型变量num记录该条路径的走的结点个数，到终点时只需要判断结点个数是否等于所有无障碍方格的个数。为了代码简洁把num初值设为无障碍方格的个数遇到一个减一，最终与0相比即可。

实现代码如下：

class Solution {
    private int[][] directs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    public int uniquePathsIII(int[][] grid) {
        boolean[][] access = new boolean[grid.length][grid[0].length];
        int startX = 0;
        int startY = 0;
        // 无障碍方格的数目
        int num = 0;
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                if(grid[i][j] == - 1){
                    continue;
                }
                num++;
                if(grid[i][j] == 1){
                    startX = i;
                    startY = j;
                }
            }
        }
        return dfs(startX, startY, grid, access, num);
    }
    public int dfs(int i, int j, int[][] grid, boolean[][] access, int num){
        if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || access[i][j] || grid[i][j] == -1){
            return 0;
        }
        num--;
        if(grid[i][j] == 2){
            return num == 0 ? 1 : 0;
        }
        int ans = 0;
        access[i][j] = true;
        for(int[] direct : directs){
            ans += dfs(i + direct[0], j + direct[1], grid, access, num);
        }
        access[i][j] = false;
        return ans;
    }
}