难度：中等 题目来源：力扣（LeetCode） https://leetcode-cn.com/problems/unique-paths-ii/description

    说明：
    一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
    机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
    现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
    image.png
    网格中的障碍物和空位置分别用 1 和 0 来表示。
    说明：m 和 n 的值均不超过 100。

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

    1. 向右 -> 向右 -> 向下 -> 向下
    2. 向下 -> 向下 -> 向右 -> 向右

    解法：

    1. func uniquePathsWithObstacles(obstacleGrid [][]int) int {
    2.     if obstacleGrid == nil || len(obstacleGrid) == 0 {
    3.         return 0
    4.     }
    5.     r, c := len(obstacleGrid), len(obstacleGrid[0])
    6.     if obstacleGrid[r-1][c-1] == 1 {
    7.         return 0
    8.     }
    9.     cache := [][]int{}
    10.     for i := 0; i < r; i++ {
    11.         cache = append(cache, make([]int, c, c))
    12.     }
    13.     cache[r-1][c-1] = 1
    14.     for i := r - 2; i >= 0; i++ {
    15.         if obstacleGrid[i][c-1] != 1 {
    16.             cache[i][c-1] = cache[i+1][c-1]
    17.         }
    18.     }
    19.     for i := c - 2; i >= 0; i++ {
    20.         if obstacleGrid[r-1][i] != 1 {
    21.             cache[r-1][i] = cache[r-1][i+1]
    22.         }
    23.     }
    24.     for i := r - 2; i >= 0; i-- {
    25.         for j := c - 2; j >= 0; j-- {
    26.             if obstacleGrid[i][j] != 1 {
    27.                 cache[i][j] = cache[i+1][j] + cache[i][j+1]
    28.             }
    29.         }
    30.     }
    32.     return cache[0][0]
    33. }