同前面的差别路径解法一样，最优方法是接纳动态规划。
此处同时接纳滚动数组优化空间。
我们用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]; }}复杂度分析
