【学会动态规划】不同路径 II（6）

**学会动态规划**

在上一篇文章中，我们讨论了动态规划的基本概念和应用。今天，我们将继续深入探索这个主题，通过解决一个经典的问题——不同路径 II（6）。

**问题描述**

给定一个 m x n 的网格，其中每个单元格都有一个数字。从左上角开始，向右或向下移动一步到达右下角的路径数为多少？请注意，每一步只能向右或向下移动。

**动态规划解决方案**

这个问题可以使用动态规划来解决。我们首先定义一个2D 数组 dp，其中 dp[i][j] 表示从左上角 (0,0) 到当前位置 (i,j) 的不同路径的数量。

def uniquePathsWithoutObstacles(m: int, n: int) -> int:
 # 初始化动态规划数组 dp = [[1]*n for _ in range(m)]
 # 从左上角开始，向右或向下移动一步到达当前位置的路径数为1 for i in range(1, m):
 for j in range(1, n):
 # 如果当前位置没有障碍，则从左边和上边来的路径数之和等于当前位置的路径数 dp[i][j] = dp[i-1][j] + dp[i][j-1]
 # 返回右下角的路径数 return dp[m-1][n-1]

**代码注释**

* 初始化动态规划数组：我们首先初始化一个2D 数组 `dp`，其中每个单元格都有值1。这是因为从左上角开始，只能向右或向下移动一步到达当前位置的路径数为1。
* 从左上角开始，向右或向下移动一步到达当前位置的路径数为1：我们使用两个嵌套循环来遍历网格中的每个单元格。如果当前位置没有障碍，则从左边和上边来的路径数之和等于当前位置的路径数。
* 返回右下角的路径数：最后，我们返回 `dp[m-1][n-1]`，即右下角的路径数。

**时间复杂度**

这个算法的时间复杂度为 O(m * n)，其中 m 和 n 是网格的行数和列数。我们需要遍历整个网格才能计算出每个单元格的路径数。

**空间复杂度**

这个算法的空间复杂度为 O(m * n)。我们使用一个2D 数组 `dp` 来存储每个单元格的路径数。

**总结**

通过动态规划，我们可以解决不同路径 II（6）问题。这个算法首先初始化一个2D 数组 `dp`，然后从左上角开始，向右或向下移动一步到达当前位置的路径数为1。如果当前位置没有障碍，则从左边和上边来的路径数之和等于当前位置的路径数。最后，我们返回右下角的路径数。

这个算法的时间复杂度为 O(m * n)，空间复杂度为 O(m * n)。