Problem statement

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

Solution

This is a classical dynamic programming problem. Let dp[i][j] be the number of paths to reach coordinate (i, j). Then first of all we check if we can reach (0, 0) coordinate. Then for each cell we check two neighbours: one above and one to the left and add this number of ways to answer. In the end we return dp[-1][-1]

Complexity

Time complexity is O(mn), because we have mn states and two transactions from one to another. Space complexity is the same.

Code

class Solution:
    def uniquePathsWithObstacles(self, M):
        m, n = len(M), len(M[0])
        dp = [[0] * n for _ in range(m)]
        dp[0][0] = int(M[0][0] == 0)
        for i, j in product(range(m), range(n)):
            if M[i][j] == 1: continue
            if i > 0: dp[i][j] += dp[i-1][j]
            if j > 0: dp[i][j] += dp[i][j-1]
                
        return dp[-1][-1]