Python/Go O(mn) by DP [w/ Hint] 有專欄解析格子點DP框架
Python/Go O(mn) by DP\n\n\u5C08\u6B04: \u5F9E\u683C\u5B50\u9EDEDP\u6846\u67B6 \u7406\u89E3Unique Path\u7CFB\u5217\u984C\u80CC\u5F8C\u7684\u539F\u7406\n\n\u4E2D\
Python/Go O(mn) by DP\n\n[\u5C08\u6B04: \u5F9E\u683C\u5B50\u9EDEDP\u6846\u67B6 \u7406\u89E3Unique Path\u7CFB\u5217\u984C\u80CC\u5F8C\u7684\u539F\u7406](https://vocus.cc/article/66092cd2fd8978000129925b)\n\n[\u4E2D\u6587\u89E3\u984C\u6587\u7AE0](https://vocus.cc/article/65114931fd89780001ce87f5)\n\n---\n\nHint:\n\n#1. Remember to **update source point as 1** (one valid path) to start traversal if source point is not blocked by obstacle\n\n#2. Here, we use **in-place update** to avoid extra space usage\n\n\n#3-a. If current grid is blocked by obstacle, then path count = 0\n\n#3-b. Otherwise, **path count to current position** = **Path count one step from left** + **Path count one step from top**.\n\n---\n\n**Implementation** by DP in Python:\n\n```\nclass Solution:\n    def uniquePathsWithObstacles(self, obstacleGrid):\n        \n        allow_to_visit = lambda x, y: (1 - obstacleGrid[y][x] )\n        \n        # height and width of matrix\n        h, w = len(obstacleGrid), len(obstacleGrid[0])\n        \n        if h * w == 0 or not allow_to_visit(0, 0):\n            \n            # Quick response for invalid cases\n            return 0\n        \n        \n        # update [0][0] as start point with one valid path\n        obstacleGrid[0][0] = 1\n        \n        ## base case: leftmost column\n        for y in range(1, h):\n            obstacleGrid[y][0] = obstacleGrid[y-1][0] * allow_to_visit(0, y)\n        \n        \n        ## base case: top row\n        for x in range(1, w):\n            obstacleGrid[0][x] = obstacleGrid[0][x-1] * allow_to_visit(x, 0)\n        \n        \n        ## general cases\n        for y in range(1, h):\n            for x in range(1, w):\n                \n                # update path count from left and top\n                obstacleGrid[y][x] = (obstacleGrid[y][x-1] + obstacleGrid[y-1][x]) * allow_to_visit(x, y)\n        \n        return obstacleGrid[h-1][w-1]\n```\n\n---\n\nShare another implementation by top-down DP in Python\n\n```\n                  \nclass Solution:\n    def uniquePathsWithObstacles(self, obstacleGrid):\n        \n        can_walk = lambda x, y: (1 - obstacleGrid[y][x] )\n        \n        # height and width of matrix\n        h, w = len(obstacleGrid), len(obstacleGrid[0])\n        \n        dp = {}\n\n        def walk(x, y):\n            \n            if (x, y) in dp:\n                # look-up DP table\n                return dp[x, y]\n\n            if not 0 <= x < w or not 0 <= y < h or not can_walk(x, y) :\n                # out-of-board, or cannot walk through\n                dp[x, y] = 0\n                return 0\n\n            if (x, y) == (0, 0):\n                # Starting point, aka base case\n                dp[x, y] = 1\n                return 1\n\n            # General cases\n            dp[x, y] = walk(x-1, y) + walk(x, y-1)\n            return dp[(x, y)]\n                    \n```\n\n---\n\n**Implementation** by DP in Golang:\n\n```\nfunc uniquePathsWithObstacles(obstacleGrid [][]int) int {\n    \n    // helper function\n    var allowToVisit func (x, y int) int\n    \n    allowToVisit = func(x, y int) int{\n        // 1 : allow to visit\n        // 0 : can not visit due to obstacle\n        return 1 - obstacleGrid[y][x]\n    }\n    \n    h, w := len(obstacleGrid), len(obstacleGrid[0])\n    \n    if h * w == 0 || allowToVisit(0, 0) == 0 {\n        // Quick response for invalid cases\n        return 0\n    }\n    \n    // update [0][0] as start point with one valid path\n    obstacleGrid[0][0] = 1\n    \n    // base case: leftmost column\n    for y := 1 ; y < h ; y++{\n        obstacleGrid[y][0] = obstacleGrid[y-1][0] * allowToVisit(0, y)\n    }\n    \n    // base case: top row\n    for x := 1 ; x < w ; x++{\n        obstacleGrid[0][x] = obstacleGrid[0][x-1] * allowToVisit(x, 0)\n    }    \n    \n    // general cases:\n    for y := 1 ; y < h ; y++{\n        for x := 1 ; x < w ; x ++{\n            \n            // update path count form left and top\n            obstacleGrid[y][x] = ( obstacleGrid[y][x-1] + obstacleGrid[y-1][x] ) * allowToVisit(x, y)\n        }\n    }\n    \n    return obstacleGrid[h-1][w-1]\n}\n```\n\n---\n\n\nRelated Leetcode challenge:\n\n[Leetcode #62 Unique Paths](https://leetcode.com/problems/unique-paths)\n\n[Leetcode #63 Unique Paths II](https://leetcode.com/problems/unique-paths-ii)\n\n[Leetcode #980 Unique Paths III](https://leetcode.com/problems/unique-paths-iii)\n
['Dynamic Programming', 'Iterator', 'Python', 'Go', 'Python3']