☆打卡算法☆LeetCode 63、不同路径 II 算法解析

发表于

这是我参与11月更文挑战的第29天，活动详情查看：2021最后一次更文挑战

推荐阅读

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定一个矩阵，从矩阵左上角移动到右下角，并且中间还有障碍物，有多少条路径。”

题目链接：

来源：力扣（LeetCode）

链接：63. 不同路径 II - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

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

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

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

image.png

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

二、解题

1、思路分析

这道题与上一题都是寻找所有的路径，都可以用动态规划的思路解题，这道题与上道题的区别在于这道题有障碍物的设置。

定义到达右下角的走法为f(m,n)，因为只能从右上角走过去，所以可以得出递归公式：

f(m,n) = f(m-1,n)+f(m,n-1)，最后加上递归结束条件，看起来就完事了。

但是，这样会造成大量的重复计算，我们可以将算法进行优化。

2、代码实现

代码参考：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
csharp复制代码public class Solution {
    public int UniquePathsWithObstacles(int[][] obstacleGrid) {
        //初始化动态规划数组
        int m = obstacleGrid.GetLength(0);
        int n = obstacleGrid[0].Length;
        int[,] ans = new int[m, n];

        //对第一行进行操作赋值
        for (int i = 0; i < n; i++)
        {
            if (obstacleGrid[0][i] == 1)
            {
                for (int j = i; j < n; j++)
                {
                    ans[0, j] = 0;
                }
                break;
            }
            else ans[0, i] = 1;
        }
        //对第一列进行操作赋值
        for (int i = 0; i < m; i++)
        {
            if (obstacleGrid[i][0] == 1)
            {
                for (int j = i; j < m; j++)
                {
                    ans[j,0] = 0;
                }
                break;
            }
            else ans[i,0] = 1;
        }
        //填充整体矩阵
        for (int i = 1; i < m; i++)
        {
            for (int j = 1; j < n; j++)
            {
                ans[i, j] = obstacleGrid[i][j] == 1 ? 0 : ans[i, j - 1] + ans[i - 1, j];
            }
        }
        return ans[m - 1, n - 1];
    }
}

image.png

3、时间复杂度

时间复杂度 ： O(nm)

其中n为网格的行数，m为网格的列数，只需要遍历一遍所有网格即可求得答案。

空间复杂度： O(m)

只需要常数级别的空间存放变量。

三、总结

动态规划的解题在很多题都会应用到。

比如说221题最大正方形，1152题地图分析等，这些题目都是以二维坐标作为状态，大多数也可以使用滚动数组进行优化。

滚动数组思想，是一种常见的动态规划优化方法，当我们定义的状态在动态规划的方程中只和某几个状态相关的时候，就可以考虑这种优化方法，目的是给空间复杂度降维。

滚动数组思想可以多学习一下。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%