一.题目
62. 不同路径 – 力扣（LeetCode）
二.思路讲解
2.1 思路讲解
机器人从网格的左上角出发，每次只能向下或向右移动一格，要到达右下角。对于右下角格子 (m, n)，它只能从它的上方格子 (m-1, n) 或左方格子 (m, n-1) 到达。因此，到达 (m, n) 的路径数就等于到达这两个相邻格子路径数之和。同理，每个格子都满足这一关系，这就形成了一个递归定义，我们可以通过递归求解。但直接递归会导致大量重复计算，例如 (i, j) 会被多次计算。
2.2 优化：记忆化搜索
通过画出递归展开图，我们会发现存在大量重叠子问题，例如计算 (3,3) 时，(2,2) 会被反复计算。为了消除重复，我们采用记忆化搜索：
-
维护一个 备忘录（二维数组）。
-
每次递归计算一个格子的路径数时，先查备忘录，若已存在则直接返回。
-
若未计算，则递归计算后存入备忘录。
-
这样每个格子只计算一次。
三.代码演示
class Solution
{
public:
int uniquePaths(int m, int n)
{
//初始化
vector<vector<int>> memo(m+1,vector<int>(n + 1));
return dfs(m,n,memo);
}
int dfs(int i,int j,vector<vector<int>>& memo)
{
//先判断备忘录有没有
if(memo[i][j])
return memo[i][j];
if(i == 0 || j == 0)
return 0;
else if(i == 1 && j == 1)
{
memo[i][j] = 1;
return memo[i][j];
}
memo[i][j] = dfs(i – 1,j,memo) + dfs(i,j – 1,memo);
return memo[i][j];
}
};
四.代码讲解
一、数据结构设计
本题需要计算从 (1,1) 到 (m,n) 的路径数。我们采用自顶向下的记忆化搜索，使用一个二维数组 memo 作为备忘录，memo[i][j] 表示从起点 (1,1) 到格子 (i,j) 的不同路径数。由于下标从 1 开始，数组大小设为 (m+1) × (n+1)，其中第 0 行和第 0 列作为哨兵，初始化为 0。
二、主函数 uniquePaths
创建一个 vector<vector<int>> memo(m+1, vector<int>(n+1, 0))，所有元素初始化为 0，表示尚未计算。
调用递归函数 dfs(m, n, memo)，从终点开始反向推导。
返回结果。
三、递归函数 dfs
dfs(i, j, memo) 表示从起点 (1,1) 到达格子 (i, j) 的路径数。执行流程如下：
1. 查备忘录
如果 memo[i][j] != 0，说明该子问题已经计算过，直接返回存储的值。这是记忆化搜索的核心优化。
2. 边界条件处理
-
越界：当 i == 0 || j == 0 时，格子不在网格内，返回 0。
-
起点：当 i == 1 && j == 1 时，起点到自身只有一条路径（不移动），将 memo[1][1] 设为 1 并返回。
3. 递归计算
对于其他格子，只能从上方 (i-1, j) 或左方 (i, j-1) 到达，因此：
memo[i][j] = dfs(i-1, j, memo) + dfs(i, j-1, memo);
将结果存入备忘录后返回。
四、关键细节
-
索引从 1 开始：题目中网格的行列通常从 1 计数，这样处理边界条件时更直观，无需额外偏移。
-
备忘录初始值 0：由于路径数不可能为 0（起点本身至少有一条路径），因此用 0 表示“未计算”是安全的。
-
递归方向：从终点 (m,n) 逆向递归到起点 (1,1)。
五、流程图
