Unique Path II

class Solution(object):
    def uniquePathsWithObstacles(self, obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        if not obstacleGrid or not obstacleGrid[0]:
            return 0
            
        # dp = [1 - obstacle for obstacle in obstacleGrid[0]]
        dp = [0] * len(obstacleGrid[0])
        for j in range(len(obstacleGrid[0])):
            # if obstacleGrid[j] == 0: 跟二维有关的 dp 时，初始化过程要记得想清楚是两个维度的坐标
            if obstacleGrid[0][j] == 0:
                dp[j] = 1
            else:
                break
        
        # firstColumStucked = False  # 要想清楚 而不是 想太多
        for i in range(1, len(obstacleGrid)):
            if obstacleGrid[i][0] == 1:
                dp[0] = 0
            for j in range(1, len(obstacleGrid[0])):
                # if obstacleGrid[i][0] == 1 or firstColumStucked:  # 要想清楚 而不是 想太多
                # if j == 0 and obstacleGrid[i][j] == 1:
                #     dp[j] = 0
                #     firstColumnStucked = True  # 要想清楚 而不是 想太多
                # dp[i] = 0 if obstacleGrid[i][j] == 1 else dp[i - 1] + dp[i] # DP 的题，特别是多维时候，状态转移方程的 i, j, k 一定要注意清楚
                dp[j] = 0 if obstacleGrid[i][j] == 1 else dp[j - 1] + dp[j] # 如果从 0 列开始更新，dp[j - 1] 会变为 dp[-1]，stack overflow 了，因此 dp 在写转移方程时不能忽视任何 index 的加减溢出问题
        return dp[-1]