62. 不同路径
前言
「力扣题解」系列致力于分享有价值的题目、探讨更优秀的解法。
这是本系列的第 2 篇题解，更多题解关注 Somnia1337@力扣。
从本篇起，新增 C++ 题解，由 @陈冥雁 提供。
基础知识
动态规划(Dynamic Programming)：将原问题分解为一系列子问题，用“小”子问题的解递推“大”子问题的解，直到解出原问题。
“programming”指的是一种表格法，并非编写计算机程序。
——《算法导论》
为了避免重复计算，通常用数组记录子问题的解，该数组习惯命名为 dp。
用动态规划解题可分为 5 步：
- 确定
dp及下标含义。 - 确定子问题解的递推公式。
- 确定
dp如何初始化。 - 确定遍历顺序。
- 举例推导。
题目描述
难度：🟡中等
一个机器人位于一个 m x n 网格的左上角 （起点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（终点在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
输入：m = 3, n = 7
输出：28题意理解
输入：int * 2，网格的长、宽。
输出：int，不同的路径数。
给定网格的长、宽，只能向下或向右移动，计算从左上角移动到右下角的不同路径总数。
举例：对长 2、宽 3 的网格，简单画图可知，共有 3 条不同的路径。
解题思路
另一种方法：组合数学
本题可以用组合数解决，在 Java 等语言中需要处理溢出问题：
而在 Python 中可以直接调用库函数 comb，一行解决本题：
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
return comb(m + n - 2, n - 1)但是，一些更复杂的相关问题难以用纯数学解决（见“相关题目”）。
本题是理解用动态规划解决路径问题的绝佳选择，因此本篇重点在于介绍动态规划，而不只是解决本题。
第 1 步：确定 dp 及下标含义
定义子问题。
子问题是，取终点之前的一个位置，计算从起点到该位置的不同路径数，例如：
共有 m * n 个子问题，要记录它们的解，因此 dp 开到 int[m][n]。
int[][] dp = new int[m][n]; // 创建dp数组dp[i][j] 表示从 到 的不同路径数。
第 2 步：确定子问题解的递推公式
找到子问题解之间的关系。
任取一个位置 ：
从 到达 的上一个可能位置有哪些？
题目规定路径只能向下或向右，因此上一个位置只可能为上侧或左侧：
所以，dp[i][j] 来源于 dp[i - 1][j] 和 dp[i][j - 1]。
从这两个位置到达 dp[i][j] 都只有 1 条路径：
因此，dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，这就是子问题解的递推公式。
原问题是所有子问题中最大的那个，最终答案为 dp[m - 1][n - 1]。
return dp[m - 1][n - 1]; // 最大子问题即为原问题第 3 步：确定 dp 如何初始化
初始化：最小子问题、递推公式无法涵盖的子问题。
考虑递推关系，dp[i][j] 从其上侧和左侧推导而来，可知第 0 行、第 0 列没有被涵盖（分别没有上一行、左一列），需要初始化。
初始化为几呢？
从 到 或 只有 1 条路径，因此第 0 行、第 0 列均填入 1。
for (int i = 0; i < m; i++) dp[i][0] = 1; // 初始化第0列
for (int j = 0; j < n; j++) dp[0][j] = 1; // 初始化第0行
第 4 步：确定遍历顺序
确保当前问题依赖的子问题已解出。
考虑递推关系，从左到右一层一层遍历，就能保证在计算 dp[i][j] 前，dp[i - 1][j] 和 dp[i][j - 1] 都已解出。
for (int i = 1; i < m; i++) { // 从1开始
for (int j = 1; j < n; j++) { // 从1开始
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; // 递推公式
}
}第 5 步：举例推导
检查思路的正确性。
以 m = 3, n = 7 为例推导：
答案为 28，符合预期，思路没有问题，就差代码实现啦！
复杂度
- 时间复杂度：。
- 空间复杂度：。
代码
代码不长，建议结合讲解仔细阅读，重新理解一下。
Java
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n]; // 创建dp数组
for (int i = 0; i < m; i++) dp[i][0] = 1; // 初始化第0列
for (int j = 0; j < n; j++) dp[0][j] = 1; // 初始化第0行
for (int i = 1; i < m; i++) { // 从1开始
for (int j = 1; j < n; j++) { // 从1开始
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; // 递推公式
}
}
return dp[m - 1][n - 1]; // 最大子问题即为原问题
}
}Python
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [[0] * n for _ in range(m)] # 创建dp数组
for i in range(0, m): # 初始化第0列
dp[i][0] = 1
for j in range(0, n): # 初始化第0行
dp[0][j] = 1
for i in range(1, m): # 从1开始
for j in range(1, n): # 从1开始
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] # 递推公式
return dp[-1][-1] # 最大子问题即为原问题C++
由 @陈冥雁 提供。
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m, vector<int>(n)); // 创建dp数组
for (int i = 0; i < m; i++) { // 初始化第0列
dp[i][0] = 1;
}
for (int j = 0; j < n; j++) { // 初始化第0行
dp[0][j] = 1;
}
for (int i = 1; i < m; i++) { // 从1开始
for (int j = 1; j < n; j++) { // 从1开始
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; // 递推公式
}
}
return dp[m - 1][n - 1]; // 最大子问题即为原问题
}
};相关题目
以下是 2 道相似的路径问题，可用动态规划解决。
63. 不同路径 II
64. 最小路径和
更多
还有一份我完成过的题单，其中标出了主观的“价值”评分，供参考：
最后
更多系列「外源推文」&「生活分享」关注公众号：