不同路径 II

题目描述：

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

示例 1：

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

1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
   示例 2：

输入：obstacleGrid = [[0,1],[0,0]]
输出：1

提示：

m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j] 为 0 或 1

思路:

时间复杂度：O(m*n),空间复杂度O(m*n)

动态规划题，只需要考虑如果是障碍物的话置为0就行

代码:

func uniquePathsWithObstacles(obstacleGrid [][]int) int {
    m,n := len(obstacleGrid),len(obstacleGrid[0])
    dp := make([][]int,m+1)
    dp[0] = make([]int,n+1)
    dp[0][1] = 1
    for i:=1;i<=m;i++{
        dp[i] = make([]int,n+1)
        for j:=1; j<=n; j++{   
            if obstacleGrid[i-1][j-1] == 1{
                dp[i][j] = 0
            }else{
                dp[i][j] = dp[i-1][j]+dp[i][j-1]
            }
            
        }
    }
    //fmt.Println(dp)
    return dp[m][n]
}

func max(a,b int)int{
    if a>b{
        return a
    }
    return b
}

代码效率：

执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：2.4 MB, 在所有 Go 提交中击败了12.46%的用户