一、题目
1、算法题目
“给定一个矩阵，从矩阵左上角移动到右下角，并且中间还有障碍物，有多少条路径。”
题目链接：
来源：力扣（LeetCode）
链接：63. 不同路径 II - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网络异常，图片无法展示
|
示例 1： 输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] 输出：2 解释： 3x3 网格的正中间有一个障碍物。 从左上角到右下角一共有 2 条不同的路径： 1. 向右 -> 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 -> 向右 复制代码
示例 2： 输入： obstacleGrid = [[0,1],[0,0]] 输出： 1 复制代码
二、解题
1、思路分析
这道题与上一题都是寻找所有的路径，都可以用动态规划的思路解题，这道题与上道题的区别在于这道题有障碍物的设置。
定义到达右下角的走法为f(m,n)，因为只能从右上角走过去，所以可以得出递归公式：
f(m,n) = f(m-1,n)+f(m,n-1)，最后加上递归结束条件，看起来就完事了。
但是，这样会造成大量的重复计算，我们可以将算法进行优化。
2、代码实现
代码参考：
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]; } } 复制代码
网络异常，图片无法展示
|
3、时间复杂度
时间复杂度 ： O(nm)
其中n为网格的行数，m为网格的列数，只需要遍历一遍所有网格即可求得答案。
空间复杂度： O(m)
只需要常数级别的空间存放变量。
三、总结
动态规划的解题在很多题都会应用到。
比如说221题最大正方形，1152题地图分析等，这些题目都是以二维坐标作为状态，大多数也可以使用滚动数组进行优化。
滚动数组思想，是一种常见的动态规划优化方法，当我们定义的状态在动态规划的方程中只和某几个状态相关的时候，就可以考虑这种优化方法，目的是给空间复杂度降维。
滚动数组思想可以多学习一下。
