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

**不同路径**

在前面的几篇文章中，我们已经学习了如何使用动态规划解决一些经典的问题，如斐波那契数列、爬楼梯等。今天我们要讲解的就是另一个经典问题——不同路径。

**什么是不同路径？**

不同路径是一道经典的算法题目，描述如下：

有一个m x n 的网格，其中每个格子都可以视为是一个点。从左上角出发（0,0），我们需要到达右下角（m-1, n-1）。在这个过程中，我们只能向右或向下移动一步。

**问题的难度**

这个问题看起来很简单，但是实际上它是有挑战性的。因为每个格子都可以选择向右或向下移动，这意味着我们需要考虑所有可能的路径，并且这些路径之间存在重叠和相互影响。

**动态规划的思路**

在解决不同路径问题时，我们可以使用动态规划来优化我们的算法。动态规划是一种通过分解大问题为小子问题，逐步求解这些子问题，然后组合结果来得到最终答案的方法。

在这个例子中，我们可以将网格视为一个m x n 的矩阵，每个格子都代表一个状态。在每一步，我们需要决定是否向右移动还是向下移动。我们可以使用一个二维数组dp来存储从左上角到当前位置的所有可能路径的数量。

**代码示例**

def uniquePaths(m, n):
 # 初始化 dp 数组，所有格子都初始化为1，因为只有一个方式可以到达每个格子（即从左上角直接移动到该格子）
 dp = [[1]*n for _ in range(m)]
 # 从第二行开始，我们需要考虑向右移动的路径数 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]

# 测试用例print(uniquePaths(3,7)) # 输出：28