python DP solution O(n) space


  • 0
    G
    class Solution(object):
        def uniquePathsWithObstacles(self, obstacleGrid):
            """
            :type obstacleGrid: List[List[int]]
            :rtype: int
            """
            m,n=len(obstacleGrid),len(obstacleGrid[0])
            flag_m,flag_n=0,0
            while flag_m<m:
                if obstacleGrid[flag_m][0]==1:break
                flag_m+=1
            while flag_n<n:
                if obstacleGrid[0][flag_n]==1:break
                flag_n+=1
            if flag_n < n:
                dp=[1]*(flag_n)+[0]*(n-flag_n)
            else:
                dp=[1]*n
            for j in range(1,m):
                if j>=flag_m:dp[0]=0
                for p in range(1,n):
                    if obstacleGrid[j][p]==1:dp[p]=0
                    else:dp[p]=dp[p]+dp[p-1]
            return dp[-1]
            
    

    Basically, we find the first obstacle in the first row (flag_n), and the first obstacle in the first column (flag_m), and then initialize the DP array using flag_n, and then iterate through every row, updating the DP array.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.