作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
题目描述
一个机器人位于一个 m x n 网格的左上角（起始点在下图标记为“Start”）。
机器人每次只能向下或向右移动一步。机器人试图达到网格的右下角（在下图标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
输入格式
- obstacleGrid：一个二维数组，表示网格，
1表示有障碍物，0表示无障碍。
输出格式
- 返回一个整数，表示所有可能的路径数量。
示例
示例 1
输入: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] 输出: 2 解释: 3x3 网格的正中间有一个障碍物。 从左上角到右下角一共有 2 条不同的路径： 1. 向右 -> 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 -> 向右
示例 2
输入: obstacleGrid = [[0,1],[0,0]] 输出: 1
方法一：动态规划
解题步骤
- 初始化状态数组：创建一个二维数组
dp，其中dp[i][j]表示到达点(i, j)的路径数量。 - 处理障碍物：如果
obstacleGrid[i][j]是1，则dp[i][j]设置为0。 - 初始化边界条件：对于第一行和第一列，如果某处有障碍物，则该处及其后的所有点都不可达，即设置为
0。 - 状态转移：对于其他位置，路径数
dp[i][j]等于从左边来的路径数加上从上面来的路径数，即dp[i][j] = dp[i-1][j] + dp[i][j-1]（前提是该位置无障碍物）。 - 返回结果：
dp[m-1][n-1]即为所求结果。
完整的规范代码
def uniquePathsWithObstacles(obstacleGrid): """ 使用动态规划解决带障碍物的不同路径问题 :param obstacleGrid: List[List[int]], 网格，1表示障碍物 :return: int, 不同的路径数量 """ if obstacleGrid[0][0] == 1: return 0 m, n = len(obstacleGrid), len(obstacleGrid[0]) dp = [[0] * n for _ in range(m)] dp[0][0] = 1 for i in range(1, m): dp[i][0] = dp[i-1][0] if obstacleGrid[i][0] == 0 else 0 for j in range(1, n): dp[0][j] = dp[0][j-1] if obstacleGrid[0][j] == 0 else 0 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] else: dp[i][j] = 0 return dp[m-1][n-1] # 示例调用 print(uniquePathsWithObstacles([[0,0,0],[0,1,0],[0,0,0]])) # 输出: 2 print(uniquePathsWithObstacles([[0,1],[0,0]])) # 输出: 1
算法分析
- 时间复杂度：(O(m * n))，需要填充一个
m行n列的矩阵。 - 空间复杂度：(O(m * n))，使用了一个同样大小的二维数组作为动态规划表。
方法二：空间优化的动态规划
解题步骤
- 使用一维数组：利用一维数组
dp来保存上一行的结果，降低空间复杂度。 - 迭代更新：对每一行使用相同的数组进行迭代更新，
dp[j]代表当前行第j列的路径数，更新公式仍为dp[j] = dp[j] + dp[j-1]，但需要考虑障碍物的影响。 - 初始化：
dp的所有元素初始化为 0，并设置第一个元素为 1（如果起点无障碍物）。
完整的规范代码
def uniquePathsWithObstacles(obstacleGrid): """ 使用一维数组进行动态规划，空间优化版本 :param obstacleGrid: List[List[int]], 网格，1表示障碍物 :return: int, 不同的路径数量 """ n = len(obstacleGrid[0]) dp = [0] * n dp[0] = 1 if obstacleGrid[0][0] == 0 else 0 for row in obstacleGrid: for j in range(n): if row[j] == 1: dp[j] = 0 elif j > 0: dp[j] += dp[j - 1] return dp[-1] # 示例调用 print(uniquePathsWithObstacles([[0,0,0],[0,1,0],[0,0,0]])) # 输出: 2 print(uniquePathsWithObstacles([[0,1],[0,0]])) # 输出: 1
算法分析
- 时间复杂度：(O(m * n))，需要迭代更新数组
m次，每次迭代有n步。 - 空间复杂度：(O(n))，使用了一个长度为
n的一维数组。### 方法三：数学组合方法（考虑障碍）
解题步骤
- 特殊情况处理：如果起点或终点有障碍物，直接返回 0。
- 动态规划组合数：利用组合数学的方法来计算路径，但由于存在障碍，此方法需要结合动态规划来计算可达的路径数。
完整的规范代码
def uniquePathsWithObstacles(obstacleGrid): """ 结合动态规划的组合数学方法处理障碍物问题 :param obstacleGrid: List[List[int]], 网格，1表示障碍物 :return: int, 不同的路径数量 """ m, n = len(obstacleGrid), len(obstacleGrid[0]) if obstacleGrid[0][0] == 1 or obstacleGrid[m-1][n-1] == 1: return 0 dp = [0] * n dp[0] = 1 for i in range(m): for j in range(n): if obstacleGrid[i][j] == 1: dp[j] = 0 elif j > 0: dp[j] += dp[j-1] return dp[-1] # 示例调用 print(uniquePathsWithObstacles([[0,0,0],[0,1,0],[0,0,0]])) # 输出: 2 print(uniquePathsWithObstacles([[0,1],[0,0]])) # 输出: 1
算法分析
- 时间复杂度：(O(m * n))，每个格子被遍历一次。
- 空间复杂度：(O(n))，使用了一维数组来保存当前行的状态。
方法四：深度优先搜索（DFS）
解题步骤
- DFS递归：从起点开始，递归地探索所有向右和向下的路径。
- 障碍物检查：如果遇到障碍物，停止在该方向的探索。
- 使用记忆化：使用哈希表来存储已计算的位置，避免重复计算。
完整的规范代码
def uniquePathsWithObstacles(obstacleGrid): """ 使用DFS和记忆化搜索解决带障碍物的不同路径问题 :param obstacleGrid: List[List[int]], 网格，1表示障碍物 :return: int, 不同的路径数量 """ m, n = len(obstacleGrid), len(obstacleGrid[0]) memo = {} def dfs(x, y): if (x, y) in memo: return memo[(x, y)] if x >= m or y >= n or obstacleGrid[x][y] == 1: return 0 if x == m-1 and y == n-1: return 1 memo[(x, y)] = dfs(x+1, y) + dfs(x, y+1) return memo[(x, y)] return dfs(0, 0) # 示例调用 print(uniquePathsWithObstacles([[0,0,0],[0,1,0],[0,0,0]])) # 输出: 2 print(uniquePathsWithObstacles([[0,1],[0,0]])) # 输出: 1
算法分析
- 时间复杂度：(O(m * n))，每个格子至多被访问一次。
- 空间复杂度：(O(m * n))，递归栈的深度以及记忆化所需的空间。
方法五：广度优先搜索（BFS）
解题步骤
- 使用队列：利用队列进行层次遍历，从起点开始探索所有可达的点。
- 累加路径数：在队列中存储每个点的路径数量，到达新点时累加。
- 障碍物处理：遇到障碍物则跳过。
完整的规范代码
from collections import deque def uniquePathsWithObstacles(obstacleGrid): """ 使用BFS解决带障碍物的不同路径问题 :param obstacleGrid: List[List[int]], 网格，1表示障碍物 :return: int, 不同的路径数量 """ if obstacleGrid[0][0] == 1: return 0 m, n = len(obstacleGrid), len(obstacleGrid[0]) queue = deque([(0, 0, 1)]) # (x, y, path_count) paths = [[0] * n for _ in range(m)] paths[0][0] = 1 while queue: x, y, path_count = queue.popleft() for dx, dy in [(1, 0), (0, 1)]: nx, ny = x + dx, y + dy if 0 <= nx < m and 0 <= ny < n and obstacleGrid[nx][ny] == 0: if paths[nx][ny] == 0: queue.append((nx, ny, paths[x][y])) paths[nx][ny] += path_count return paths[m-1][n-1] # 示例调用 print(uniquePathsWithObstacles([[0,0,0],[0,1,0],[0,0,0]])) # 输出: 2 print(uniquePathsWithObstacles([[0,1],[0,0]])) # 输出: 1
算法分析
- 时间复杂度：(O(m * n))，每个节点最多入队出队一次。
- 空间复杂度：(O(m * n))，队列和路径计数数组的空间需求。
不同算法的优劣势对比
| 特征 | 方法一: 动态规划 | 方法二: 空间优化DP | 方法三: 数学组合 | 方法四: DFS | 方法五: BFS |
| 时间复杂度 | (O(m * n)) | (O(m * n)) | (O(m * n)) | (O(m * n)) | (O(m * n)) |
| 空间复杂度 | (O(m * n)) | (O(n)) | (O(1)) | (O(m * n)) | (O(m * n)) |
| 优势 | 直观，易理解 | 空间效率高 | 计算最快，非迭代 | 灵活，适用于复杂边界 | 层次清晰，适用于大规模 |
| 劣势 | 空间占用高 | 优化限于列 | 对大数处理有限制 | 时间空间成本高 | 需要额外存储空间 |
应用示例
游戏开发中的路径发现：
在策略游戏或迷宫游戏中，开发者可以利用这些算法来计算从起点到终点的所有可能路径，为游戏的AI决策提供支持，比如在自动生成的迷宫中计算最优路径或在战略游戏中规划单位的行动路线。这些算法提供了不同的效率和实现复杂度，使得开发者可以根据具体游戏场景和性能要求选择最适合的方法。
欢迎关注微信公众号 数据分析螺丝钉
