62. 不同路径中等一个机器人位于一个m x n网格的左上角 起始点在下图中标记为 “Start” 。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish” 。问总共有多少条不同的路径示例 1输入m 3, n 7 输出28示例 2输入m 3, n 2 输出3 解释 从左上角开始总共有 3 条路径可以到达右下角。 1. 向右 - 向下 - 向下 2. 向下 - 向下 - 向右 3. 向下 - 向右 - 向下示例 3输入m 7, n 3 输出28示例 4输入m 3, n 3 输出6提示1 m, n 100题目数据保证答案小于等于2 * 109 核心笔记不同路径 (Unique Paths - DFS)1. 核心思想 (一句话总结)“溯源游戏我想知道走到终点(i, j)有几条路就问问它的‘上家’——它头顶的格子(i-1, j)和左边的格子(i, j-1)各有几条路。”状态定义dfs(i, j)表示从起点(0, 0)走到(i, j)的路径总数。转移方程dfs(i, j) dfs(上) dfs(左)。加法原理路径总数等于所有可能的来源之和。2. 算法流程 (DFS Memo)入口 (Entry)从终点(m-1, n-1)开始调用dfs逆流而上寻找起点。初始化memo数组0 表示未计算因为路径数至少为 1所以 0 是安全的初始值。递归 (Recursion)越界检查i 0或j 0说明撞墙了这条路不通返回 0。Base Casei 0 j 0终于回溯到了起点说明找到了一条合法路径返回 1。查表memo[i][j] ! 0说明这个格子的路径数算过了直接返回。计算 (Calculate)res dfs(i-1, j) dfs(i, j-1)。存入memo[i][j]并返回。 代码回忆清单// 题目LC 62. Unique Paths class Solution { public int uniquePaths(int m, int n) { // memo[i][j]: 到达坐标 (i, j) 的路径数 // 0 表示未计算因为只要能到路径数至少是 1 int[][] memo new int[m][n]; // 从终点开始往回推 return dfs(m - 1, n - 1, memo); } private int dfs(int i, int j, int[][] memo) { // 1. 越界检查 (撞墙) // 比如在第一行往上看 (i-1 0)是没有路的 if (i 0 || j 0) { return 0; } // 2. Base Case: 回到了起点 // 找到了一条路贡献 1 个计数 if (i 0 j 0) { return 1; } // 3. 记忆化查表 if (memo[i][j] ! 0) { return memo[i][j]; } // 4. 状态转移来自上面 来自左边 return memo[i][j] dfs(i - 1, j, memo) dfs(i, j - 1, memo); } }⚡ 快速复习 CheckList (易错点)[ ]为什么 Base Case 返回 1因为(0,0)本身就是一种“到达”的状态或者说不需要移动就在起点了。数学上加法的单位元是 0越界乘法的单位元是 1组合数。这里是累加路径当递归触底时代表“这是一条有效路径”所以计数 1。[ ]时间复杂度。虽然是递归但有 Memo 保证每个格子只计算一次。这和双重循环填 DP 表的计算量是完全一样的。[ ]能不能优化空间递归写法因为栈深度的原因空间复杂度是 (数组) (栈)。如果面试官要求优化空间需要改写成迭代版 (DP)滚动数组可以将空间降为 。️ 中文数字演练m 3 (行), n 2 (列)终点是(2, 1)。启动dfs(2, 1):需要dfs(1, 1)(上) dfs(2, 0)(左)。分支 A:dfs(1, 1):需要dfs(0, 1)dfs(1, 0)。dfs(0, 1)(第一行往右): 最终追溯到起点返回1。dfs(1, 0)(第一列往下): 最终追溯到起点返回1。结果:1 1 2。记录memo[1][1] 2。分支 B:dfs(2, 0): (最下面一行)需要dfs(1, 0)(上) dfs(2, -1)(左, 越界)。dfs(1, 0): 之前算过吗如果在递归树中没共享会重算追溯到起点返回1。dfs(2, -1): 返回0。结果:1 0 1。记录memo[2][0] 1。汇总dfs(2, 1):dfs(1, 1)(2) dfs(2, 0)(1) 3。最终结果: 3。 核心笔记不同路径 (Unique Paths - DP Iterative) 递推1. 核心思想 (一句话总结)“网格填数每一个格子的路径数都等于它‘正上方格子’和‘正左方格子’的路径数之和汇流原理。”状态定义f[i1][j1]对应实际网格(i, j)的路径数。转移方程f[curr] f[up] f[left]。哨兵技巧f[0][1] 1是唯一的“火种”。当计算起点(0,0)对应的f[1][1]时它会等于f[0][1] (1) f[1][0] (0) 1从而成功初始化起点。2. 算法流程 (DP 迭代)定义 (Def)创建f[m 1][n 1]。多出来的一行一列默认是 0充当“墙壁”。点火 (Seed)f[0][1] 1。这是为了给起点(0,0)提供初始值的。或者设置f[1][0] 1也可以效果一样。填表 (Loop)i从 0 到m-1j从 0 到n-1。f[i1][j1]当前格 f[i][j1]上 f[i1][j]左。由于有了哨兵循环内完全不需要if (i 0)这种边界检查。结果 (Result)返回f[m][n]。 代码回忆清单// 题目LC 62. Unique Paths class Solution { public int uniquePaths(int m, int n) { // 1. DP 表多开一行一列避免处理边界条件 // 默认初始化为 0 int[][] f new int[m 1][n 1]; // 2. Base Case (哨兵点火) // 这是一个虚拟的起点的上方值为 1 // 当计算 f[1][1] (即起点) 时它会变成 1 0 1 f[0][1] 1; // 3. 遍历实际的网格坐标 (0 到 m-1, 0 到 n-1) for (int i 0; i m; i) { for (int j 0; j n; j) { // 4. 状态转移 // i1, j1 是 DP 表中的坐标 // i, j1 是上i1, j 是左 f[i 1][j 1] f[i][j 1] f[i 1][j]; } } // 5. 返回右下角 return f[m][n]; } }⚡ 快速复习 CheckList (易错点)[ ]为什么f的大小是m1, n1为了在处理f[1][...](实际第0行) 时能直接访问f[0][...]而不越界。f[0]行全是 0相当于网格外的墙壁除了我们特意设置的那个 1。[ ]f[0][1] 1放在循环里行吗不行。它必须在循环开始前设置好作为推导的源头。如果放在循环里每次都重置逻辑就乱了。[ ]空间复杂度优化当前是 。可以优化成一维数组int[] f new int[n 1](滚动数组)。f[j] f[j] f[j-1](新值 旧值(上) 新值(左))。️ 数字演练m 3 (行), n 2 (列)初始化:f是 4x3 的矩阵。全 0。设置f[0][1] 1。i0 (实际第1行):j0:f[1][1] f[0][1](1) f[1][0](0) 1。 (起点)j1:f[1][2] f[0][2](0) f[1][1](1) 1。 (一直往右走)i1 (实际第2行):j0:f[2][1] f[1][1](1) f[2][0](0) 1。 (一直往下走)j1:f[2][2] f[1][2](1) f[2][1](1) 2。 (上左)i2 (实际第3行):j0:f[3][1] f[2][1](1) f[3][0](0) 1。j1:f[3][2] f[2][2](2) f[3][1](1) 3。返回:f[3][2] 3。
