[dynamic programming] different paths 2

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

A robot is in a m x n The top left corner of the grid , The robot can only move down or right one step at a time . The robot tries to reach the bottom right corner of the grid , Now consider the obstacles in the grid . So how many different paths will there be from the top left corner to the bottom right corner ？

Definition ：$dp[i][j]$ Indicates a slave index number $(0,0)$ To index number $(i,j)$ The number of paths taken

The border ： First row and first column ,$dp[0][0]$​​​ Can only be 1. meanwhile , Because you can only go down or right , Therefore, both the first row and the first column can be calculated directly , by 1, If there are obstacles , by 0.

State transition equation ：$dp[i][j]=\{\begin{array}{ll}dp[i-1][j]+dp[i][j-1],& obstacleGrid[i][j]=0\\ 0,& obstacleGrid[i][j]\ne 0\end{array}$​​​​​

explain ： Current value , Equal to the sum of the previous row and the left column , If there are obstacles , by 0

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid):

        m = len(obstacleGrid)
        n = len(obstacleGrid[0])

        dp = [[0 for i in range(n)] for j in range(m)]

        for i in range(n):
            if obstacleGrid[0][i]==1:
                break
            dp[0][i] = 1
        for i in range(m):
            if obstacleGrid[i][0]==1:
                break
            dp[i][0] = 1

        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j] == 0:
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        return dp[m-1][n-1]