一、简介

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

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

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

题目来源：牛客

二、实现

// a[i][j] = a[i][j-1] + a[i-1][j]

func uniquePathsWithObstacles(obstacleGrid [][]int) int {
   if len(obstacleGrid) == 0 || obstacleGrid[0][0] == 1 {
      return 0
   }

   m := len(obstacleGrid)
   n := len(obstacleGrid[0])
   dp := make(map[int]map[int]int)
   for i:=0; i< m; i++ {
      dp[i]= make(map[int]int)
   }

   dp[0][0] = 1

   // 第一行
   for i:=1; i<n; i++ {
      if obstacleGrid[0][i] == 1 {
         break
      }

      dp[0][i] = 1
   }
   // 第一列
   for i :=1; i< m; i++ {
      if obstacleGrid[i][0] ==1 {
         break
      }

      dp[i][0]= 1
   }

   for i := 1; i < m; i++ {
      for j := 1; j < n; j++ {
         if obstacleGrid[i][j] != 1 {
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
         }
      }
   }
   return dp[m-1][n-1]
}