【Leetcode】63. Unique Paths II

跟62. Unique Paths 题大致相同。只不过路径上有障碍物，不能经过障碍物。
考虑dp[i][j],如果该格子有障碍物，那么dp[i][j] = 0,否则 dp[i][j] = dp[i-1][j] + dp[i][j-1].
这样做的好处就是不用管左边或者上面的格子是否有障碍物，有的话其对应的dp值为0.

方法1 DP法

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        dp = [[0]*len(obstacleGrid[0]) for i in range(len(obstacleGrid))]
        for i in range(len(obstacleGrid)):
            for j in range(len(obstacleGrid[0])):
                if i + j == 0:
                    dp[i][j] = 0 if obstacleGrid[i][j] else 1
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1] if obstacleGrid[i][j] == 0 else 0
        return dp[-1][-1]

方法2 递归

注意这里和62. Unique Paths 还有一点不同的是，62题给的是m n 并且没有障碍物，所以当m 或 n是一定返回的是1（不需要再往前判断了，因为只有一条路径），递归可以不用递归到起始位置，
但这一题给了障碍物的数组，不能判断起点到当前位置是否可达，还得往前递归，这道题一定要递归到起点，除非在起点前返回的都是0，所以在递归的时候可能会产生边界越界的情况，要进行判断并返回 0
TLE

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid):
        return self.helper(len(obstacleGrid)-1, len(obstacleGrid[0])-1, obstacleGrid)

    def helper(self, m,n, obstacleGrid):
    #越界处理
        if m < 0 or n < 0:
            return 0
        if m == 0 and n == 0:
            return 1 if obstacleGrid[m][n] != 1 else 0
        else:
            return self.helper(m-1, n, obstacleGrid) + self.helper(m, n-1, obstacleGrid) \
                if obstacleGrid[m][n] != 1 else 0

改进，dict存值

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid):
        self.dict = {}
        return self.helper(len(obstacleGrid)-1, len(obstacleGrid[0])-1, obstacleGrid)

    def helper(self, m,n, obstacleGrid):
        if m < 0 or n < 0:
            return 0
        if m == 0 and n == 0:
            return 1 if obstacleGrid[m][n] != 1 else 0
        else:
            key = str(m) + "-" + str(n)
            if key not in self.dict:
                self.dict[key] = self.helper(m-1, n, obstacleGrid) + self.helper(m, n-1, obstacleGrid) \
                if obstacleGrid[m][n] != 1 else 0
            return  self.dict[key]