【LeetCode 中等題】34-不同路徑II

題目描述：一個機器人位于一個 m x n 網格的左上角 （起始點在下圖中标記為“Start” ）。機器人每次隻能向下或者向右移動一步。機器人試圖達到網格的右下角（在下圖中标記為“Finish”）。現在考慮網格中有障礙物。那麼從左上角到右下角将會有多少條不同的路徑？

網格中的障礙物和空位置分别用 

1

 和 

 來表示。

說明：m 和 n 的值均不超過 100。

示例 1:

輸入:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
輸出: 2
解釋:3x3 網格的正中間有一個障礙物。
從左上角到右下角一共有 2條不同的路徑：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
           

解法1。思路大緻相似，但是要考慮到有障礙的情況就置為0，邊界情況要考慮清楚，不是之前逐個賦1，注意觀察差別。

class Solution(object):
    def uniquePathsWithObstacles(self, obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        if m<=0 or n<=0 or obstacleGrid[0][0]==1:
            return 0
        dp = [[0 for _ in range(n)] for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if obstacleGrid[i][j] == 1:
                    dp[i][j] = 0
                elif i==0 and j==0:
                    dp[i][j] = 1
                elif i==0 and j>0:
                    dp[i][j] = dp[i][j-1]
                elif i>0 and j==0:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = dp[i-1][j]+dp[i][j-1]
        return dp[-1][-1]
           

參考連結：http://www.cnblogs.com/grandyang/p/4353680.html