一、题目
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、代码实现
代码参考：
代码语言：javascript复制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题地图分析等，这些题目都是以二维坐标作为状态，大多数也可以使用滚动数组进行优化。
滚动数组思想，是一种常见的动态规划优化方法，当我们定义的状态在动态规划的方程中只和某几个状态相关的时候，就可以考虑这种优化方法，目的是给空间复杂度降维。
滚动数组思想可以多学习一下。
