一、问题描述

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

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

网格中的障碍物和空位置分别用 1 和 0 来表示。 注意： m 和 n 的值均不超过 100。

二、方案一：动态规划

1、思路

与第62题类似，我们使用动态规划方法，但需要考虑障碍物的影响。

• 定义状态：dp[i][j] 表示从左上角到达位置 (i, j) 的不同路径数量。
• 状态转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]，如果 (i, j) 位置没有障碍物。
• 如果 (i, j) 位置有障碍物，则 dp[i][j] = 0。
• 初始化：第一行和第一列的 dp 值为 1，除非遇到障碍物。
• 返回值：dp[m-1][n-1]，即右下角的路径数量。

2、代码实现

func uniquePathsWithObstacles(obstacleGrid [][]int) int {
    m, n := len(obstacleGrid), len(obstacleGrid[0])
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
    }
    // 初始化第一行和第一列
    for i := 0; i < m && obstacleGrid[i][0] == 0; i++ {
        dp[i][0] = 1
    }
    for j := 0; j < n && obstacleGrid[0][j] == 0; j++ {
        dp[0][j] = 1
    }
    // 动态规划填表
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            if obstacleGrid[i][j] == 0 {
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
            }
        }
    }
    return dp[m-1][n-1]
}

3、复杂度分析

• 时间复杂度：O(m*n)，我们需要遍历整个网格。
• 空间复杂度：O(m*n)，用于存储动态规划表。

三、方案二：空间优化动态规划

1、思路

在方案一中，我们使用了一个二维数组来存储动态规划的状态。实际上，我们只需要存储当前行和上一行的状态，因此可以将空间复杂度从 O(m*n) 降低到 O(n)。

2、代码实现

func uniquePathsWithObstacles(obstacleGrid [][]int) int {
    m, n := len(obstacleGrid), len(obstacleGrid[0])
    dp := make([]int, n)
    dp[0] = 1
    // 动态规划填表
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if obstacleGrid[i][j] == 1 {
                dp[j] = 0
            } else if j > 0 {
                dp[j] += dp[j-1]
            }
        }
    }
    return dp[n-1]
}

3、复杂度分析

• 时间复杂度：O(m*n)，我们需要遍历整个网格。
• 空间复杂度：O(n)，只需要存储当前行和上一行的状态。

四、总结

方案	时间复杂度	空间复杂度	说明
动态规划	O(m*n)	O(m*n)	适用于一般情况，易于理解和实现
空间优化动态规划	O(m*n)	O(n)	在空间复杂度上进行了优化

根据题目要求，两种方案均能满足需求。如果对空间复杂度有要求，建议使用空间优化动态规划方法。