二刷 LeetCode：62. 不同路径 64. 最小路径和 复盘笔记

目录

一、62. 不同路径

题目回顾

思路复盘

1. DP 思路

2. Python 代码实现

3. 空间优化（O (n)）

易错点 & 二刷心得

二、64. 最小路径和

题目回顾

思路复盘

1. DP 思路

2. Python 代码实现（原地修改，空间 O (1)）

3. 一维空间优化（O (n)）

易错点 & 二刷心得

三、两道题的共性总结 & 二刷收获

这两道题是二维动态规划的入门经典，也是面试中高频考点，非常适合作为 DP 算法的练手模板题。二刷时，我们重点拆解思路、对比不同解法，并总结通用的 DP 解题框架。

一、62. 不同路径

题目回顾

一个机器人位于一个m x n网格的左上角，它每次只能向下或者向右移动一步。机器人试图达到网格的右下角。问总共有多少条不同的路径？

思路复盘

这道题是典型的二维动态规划问题，核心是找到状态转移方程。

1. DP 思路

• 状态定义：dp[i][j]表示从起点(0,0)走到(i,j)的不同路径数。
• 状态转移：因为只能从上方(i-1,j)或左方(i,j-1)过来，所以：dp[i][j] = dp[i-1][j] + dp[i][j-1]
• 初始状态：
  • 第一行dp[0][j]：只能一直向右走，所以路径数都为 1。
  • 第一列dp[i][0]：只能一直向下走，所以路径数都为 1。
• 结果：dp[m-1][n-1]

2. Python 代码实现

python

运行

def uniquePaths(m: int, n: int) -> int: # 创建DP表 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]

3. 空间优化（O (n)）

由于dp[i][j]只依赖上一行的dp[i-1][j]和当前行的dp[i][j-1]，我们可以用一维数组滚动更新：

python

运行

def uniquePaths(m: int, n: int) -> int: dp = [1] * n for i in range(1, m): for j in range(1, n): dp[j] = dp[j] + dp[j-1] return dp[-1]

易错点 & 二刷心得

1. 初始状态处理：第一行和第一列必须初始化为 1，这是很多新手容易漏掉的细节。
2. 方向限制：题目规定只能向右或向下移动，这是 DP 转移方程成立的前提，如果允许其他方向，解法会完全不同。
3. 优化技巧：二维 DP 转一维的关键在于理解 “滚动更新”，用一维数组覆盖上一行的数据，大幅降低空间复杂度。

二、64. 最小路径和

题目回顾

给定一个包含非负整数的m x n网格grid，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。每次只能向下或者向右移动一步。

思路复盘

这道题是上一题的进阶版，同样是二维 DP，但目标从 “求路径数” 变成了 “求路径和的最小值”。

1. DP 思路

• 状态定义：dp[i][j]表示从起点走到(i,j)的最小路径和。
• 状态转移：到达(i,j)只能从上方或左方来，所以：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
• 初始状态：
  • 第一行：只能从左边来，dp[0][j] = dp[0][j-1] + grid[0][j]
  • 第一列：只能从上方来，dp[i][0] = dp[i-1][0] + grid[i][0]
• 结果：dp[m-1][n-1]

2. Python 代码实现（原地修改，空间 O (1)）

python

运行

def minPathSum(grid: list[list[int]]) -> int: m, n = len(grid), len(grid[0]) # 初始化第一行 for j in range(1, n): grid[0][j] += grid[0][j-1] # 初始化第一列 for i in range(1, m): grid[i][0] += grid[i-1][0] # 填充表格 for i in range(1, m): for j in range(1, n): grid[i][j] += min(grid[i-1][j], grid[i][j-1]) return grid[m-1][n-1]

3. 一维空间优化（O (n)）

python

运行

def minPathSum(grid: list[list[int]]) -> int: m, n = len(grid), len(grid[0]) dp = [0] * n dp[0] = grid[0][0] # 初始化第一行 for j in range(1, n): dp[j] = dp[j-1] + grid[0][j] for i in range(1, m): dp[0] += grid[i][0] # 更新第一列 for j in range(1, n): dp[j] = min(dp[j], dp[j-1]) + grid[i][j] return dp[-1]

易错点 & 二刷心得

1. 原地修改：这道题可以直接修改原数组作为 DP 表，空间复杂度降到 O (1)，这是面试中加分的优化技巧。
2. 初始状态的累加：第一行和第一列的初始化不是简单的赋值，而是需要累加前面的路径和。
3. 和上一题的对比：两道题的 DP 框架完全一致，只是状态转移方程从 “相加” 变成了 “取最小再相加”，这体现了 DP 题目的 “万变不离其宗”。

三、两道题的共性总结 & 二刷收获

1. 二维 DP 的通用解题模板：
   1. 定义状态：明确dp[i][j]的含义。
   2. 找出转移方程：根据题目限制（如移动方向），写出dp[i][j]与之前状态的关系。
   3. 初始化边界：处理第一行、第一列等特殊情况。
   4. 按顺序填充：通常按行优先或列优先的顺序遍历表格。
   5. 优化空间：思考是否可以用一维数组或原地修改优化空间。
2. 面试高频考点：
   • 这类网格 DP 问题是动态规划入门的必考题，重点考察状态定义和转移方程的推导。
   • 优化空间复杂度的思路（从二维到一维，再到原地修改）是面试中常被追问的点。
3. 二刷的意义：
   • 第一次做可能只会暴力 DP，二刷时要重点思考优化空间和通用模板。
   • 这两道题可以作为所有网格 DP 问题的 “母题”，后续遇到类似题目（如带障碍物、带权重的网格），都可以套用这个框架。