【LeetCode】0063 不同路径II

https://leetcode-cn.com/problems/unique-paths-ii/

# -*- coding:utf-8 -*-

class Solution(object):
    def uniquePathsWithObstacles(self, obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        def is_available(x, y):
            """
            验证当前位置是否可达
            :param x:
            :param y:
            :return:
            """
            if x < len(obstacleGrid) and y < len(obstacleGrid[0]) and obstacleGrid[x][y] == 0:
                return True
            else:
                return False
        def dfs(x, y):
            """
            深度优先遍历
            :param x:
            :param y:
            :return:
            """
            if x == len(obstacleGrid) - 1 and y == len(obstacleGrid[0]) - 1:
                return 1
            res = 0
            for ii, jj in [(0, 1), (1, 0)]:
                if is_available(x + ii, y + jj):
                    res += dfs(x + ii, y + jj)
            return res
        # if len(obstacleGrid) == 1:
        #     if sum(obstacleGrid[0]) >= 1:
        #         return 0
        #     return 1
        if obstacleGrid[0][0] == 1:
            return 0
        res = dfs(0, 0)
        return res
if __name__ == '__main__':
    obta = [
        [0, 0, 0],
        [0, 1, 0],
        [0, 0, 0]
    ]
    print(Solution().uniquePathsWithObstacles(obta))

思路：刚开始我想的是深搜，虽然能完成，但是超时了，那就dp呗。

dp的思路是先处理一行，如果当前位置是路障，则为0，否则为左和上的和。

建议采用多一行列的dp数组来统一化操作。

也可以使用优化内存的dp数组。dp代表当前行的相关信息，因为第一列总要和当前行的上一行一致（因为只能向下到这里），所以完全可以直接继续使用上一行的dp状态来计算下一行。

这里之所以dp初始化为m+1个就是要当j==0时j-1能够统一操作，放到[1]前面也一样

def uni(self, obstacleGrid):
    m, n = len(obstacleGrid[0]), len(obstacleGrid)
    dp = [1] + [0] * m
    for i in range(0, n):
        for j in range(0, m):
            dp[j] = 0 if obstacleGrid[i][j] else dp[j] + dp[j - 1]
    return dp[-2]