Leetcode 63. Unique Paths II

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

Evolved version of last problem. Still we can use DP, when see a 1 in the board, we put a 0. Note the case of obstacles on initial top and left edges. Also when the start or end point is blocked, there is no way to go through.

This time we can use a rolling list way[n] to replace dp[i][j] because we only care about last point's value, so the values before can be dropped once they have been calculated, which can save some spaces.

Solution:

# T:O(m*n) S:O(n)
class Solution:
    # @param obstacleGrid, a list of lists of integers
    # @return an integer
    def uniquePathsWithObstacles(self, obstacleGrid):
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        ways = [0] * n
        
        if obstacleGrid[0][0] == 0:
            ways[0] = 1
            
        for j in xrange(1, n):
            if obstacleGrid[0][j] == 1:
                ways[j] = 0
            else:
                ways[j] = ways[j - 1]
        
        for i in xrange(1, m):
            if obstacleGrid[i][0] == 1:
                ways[0] = 0
                
            for j in xrange(1, n):
                if obstacleGrid[i][j] == 1:
                    ways[j] = 0
                else:
                    ways[j] += ways[j - 1]
        
        return ways[n - 1]

Run Time: 56 ms