LeetCode题解：不同路径II

题目描述

一个机器人位于一个m×n网格的左上角。
机器人每次只能向下或者向右移动一步。机器人试图到达网格的右下角 。
现在考虑网格中有障碍物。那么从左上角到右下角 将会有多少条不同的路径呢？
网格中的障碍物和空位置分别用1和0表示。

示例

来自LeetCode

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：

1. 向右 -> 向右 -> 向下 -> 向下
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[i][j]==1){
                    f[j]=0;
                    continue;
                }
                if(j>=1&&obstacleGrid[i][j-1]==0){
                    f[j]+=f[j-1];
                }
            }
        }
        return f[m-1];
    }
}

复杂度分析

• 时间复杂度：O(nm),其中n为网格的行数，m为网格的列数。
• 空间复杂度：O(m)。利用滚动数组优化，我们可以只用O(m)大小的空间来记录当前行的通路值。