标题形貌
一个呆板人位于一个m×n网格的左上角。
呆板人每次只能向下大概向右移动一步。呆板人试图到达网格的右下角 。
如今思量网格中有停滞物。那么从左上角到右下角 将会有多少条差别的路径呢？
网格中的停滞物和空位置分别用1和0体现。
示例
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
表明：3x3 网格的正中央有一个停滞物。
从左上角到右下角一共有 2 条差别的路径：
- 向右 -> 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右 -> 向右
方法思绪
同前面的差别路径解法一样，最优方法是接纳动态规划。
此处同时接纳滚动数组优化空间。
我们用f(i,j)来体现从坐标(0,0)到坐标(i,j)的路径数，u(i,j)体现坐标(i,j)是否可行，假如坐标(i,j)有停滞物，u(i,j)=0，否则u(i,j)=1。
由于呆板人只能向下大概向右移动，以是坐标(0,0)到坐标(i,j)的路径总数的值只能取决于坐标(0,0)到坐标(i-1,j)的路径总数和从坐标(0,0)到坐标(i,j-1)的路径总数，即f(i,j)只能通过f(i-1,j)和坐标f(i,j-1)转移得到。当坐标(i,j)自己有停滞物的时间，任何路径都到不了f(i,j)，此时f(i,j)=0。
class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { int n = obstacleGrid.length; int m = obstacleGrid[0].length; int[] f = new int[m]; f[0]= obstacleGrid[0][0]==0?1:0; for(int i=0;i<n;++i){ for(int j=0;j<m;++j){ if(obstacleGrid[j]==1){ f[j]=0; continue; } if(j>=1&&obstacleGrid[j-1]==0){ f[j]+=f[j-1]; } } } return f[m-1]; }}复杂度分析
- 时间复杂度：O(nm),此中n为网格的行数，m为网格的列数。
- 空间复杂度：O(m)。使用滚动数组优化，我们可以只用O(m)巨细的空间来记载当前行的通路值。
|
