题目

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

说明：m?和 n 的值均不超过 100。

示例?1:

输入:
[
? [0,0,0],
? [0,1,0],
? [0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

解答

# 动态规划转换方程:
# ① dp[i][j] = dp[i-1][j] + dp[i][j-1]  (i>0 and j>0)
# ② dp[i][j] = 1    ((i=0 and dp[i][j-1]!=0) or (j=0 and dp[i-1][j]!=0)), 处理边界, 要求到(i,j)前一个位置路径数不是0, 否则就代表这条路被阻断了
# dp[i][j]表示能到(i, j)位置的路径条数. 条件②的dp[i][j-1]!=0、dp[i-1][j]!=0是必须的，否则有反例：[[0, 0], [1, 1], [0, 0]]

class Solution:
    # 二维dp
    def uniquePathsWithObstacles(self, nums):
        if not nums or nums[0][0] == 1:
            return 0
        rows = len(nums)
        cols = len(nums[0])
        dp = [[0 for _ in range(cols)] for _ in range(rows)]

        for i in range(rows):
            for j in range(cols):
                if i == 0 and j == 0:  # 处理左上角
                    dp[i][j] = 1
                    continue
                if nums[i][j] == 1:  # 障碍物
                    dp[i][j] = 0
                    continue

                if (j == 0 and dp[i-1][j] != 0) or (i == 0 and dp[i][j-1] != 0):  # 处理左、上边界
                    dp[i][j] = 1
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[-1][-1]



# # 深搜超时，暴风哭泣辽。。
# class Solution:
#     def __init__(self):
#         self.rows = 0
#         self.cols = 0
#         self.book = [[]]
#         self.nums = [[]]
#         self.cnt = 0
#         self.next = [
#             [0, 1],
#             [1, 0]
#         ]
#
#     def uniquePathsWithObstacles(self, obstacleGrid):
#         if not obstacleGrid:
#             return 0
#         self.nums = obstacleGrid
#         self.rows = len(obstacleGrid)
#         self.cols = len(obstacleGrid[0])
#
#         self.book = [[0 for _ in range(self.cols)] for _ in range(self.rows)]
#         self.book[0][0] = 1
#         self.dfs(0, 0)
#         return self.cnt
#
#     def dfs(self, x, y):
#         if x == self.rows-1 and y == self.cols-1:
#             self.cnt += 1
#             return
#         for i in range(2):
#             tx = x + self.next[i][0]
#             ty = y + self.next[i][1]
#             if 0 <= tx < self.rows and 0 <= ty < self.cols and self.book[tx][ty] == 0 and self.nums[tx][ty] == 0:
#                 self.book[tx][ty] = 1
#                 self.dfs(tx, ty)
#                 self.book[tx][ty] = 0

相似题目

剑指 Offer 47. 礼物的最大价值

【Leetcode 动态规划、深搜】 不同路径 II（63）

原文：https://www.cnblogs.com/ldy-miss/p/13255255.html