刷力扣的人应该都清楚，动态规划是绕不过去的一座山。而“力扣32.最长有效括号、62.不同路径、64.最小路径和”这三道题，恰好构成了一条很典型的DP进阶线：从一维状态设计到二维状态设计，从计数类问题到最优值问题，从基础推导到滚动数组优化。我身边很多人都是按这个顺序连续刷的，刷完之后对DP的状态定义、转移方程、边界初始化会有一种“通了”的感觉。这篇文章就把这三道题一次性讲透，包括每道题的思考过程、代码实现、易错点，以及我实际刷题中踩过的坑和验证过的技巧，希望能帮你少走弯路。
1. 为什么把这三道题放在一起刷
1.1 三题背后的共同主线
先说一个整体判断：这三道题放在一起，不是随便凑数的。
最长有效括号要求的是“最长的合法括号子串长度”，这是一个一维数组上的状态转移问题；不同路径要求的是“从左上角到右下角的方案总数”，这是一个二维网格上的计数问题；最小路径和要求的则是“从左上角到右下角的最小数字总和”，同样在二维网格上，但目标是求最优值而不是计数。从一维到二维，从“求最长”到“求方案数”再到“求最小代价”，恰好对应了动态规划学习的几个关键台阶。
我在实际带人刷题时发现，很多初学者一上来就啃背包、区间DP这种复杂模型，结果被状态设计劝退。反而像这三道题这样，从最基础的线性DP和网格DP入手，先把“状态定义”和“转移方程”这两个基本功打牢，后面遇到难题才有拆解的底气。
1.2 适合什么样的人参考
这份内容不是只给大佬看的，而是给那些“DP入门到中等进阶之间”的刷题者准备的。如果你已经会写简单的递归、知道什么是记忆化搜索，但遇到DP题还是不知道状态怎么开、转移怎么写，那么这三道题就是很好的练手材料。如果你正准备面试，这三道题在面试中出现频率也相当高，尤其是不同路径和最小路径和，属于“必须一遍写对”的题目。
我会把每一道题拆成“思路推导—实现细节—常见错误—优化方法”四个层次来讲，这样无论你是第一遍刷还是二刷复习，都能找到自己需要的部分。
2. 力扣32：最长有效括号，一维DP和栈的两种解法
2.1 题目到底在问什么
给定一个只包含(和)的字符串，找出最长有效括号子串的长度。注意是“连续子串”，也就是说子串里的每一个括号都必须有效匹配。
有效括号串的定义很直观：任意前缀中左括号数量不少于右括号数量，并且整个串中左右括号数量相等。理解这个定义是解题的第一步。
我第一次做这道题时第一反应是“用栈模拟匹配就行”，写完后发现如果要的是“最长连续匹配长度”，仅仅匹配完所有成对括号还不够，因为中间可能被不匹配的括号隔断。比如()(()，栈可以把前两个括号配对，但是后面(和)虽然也是成对的，整个子串却不连续，所以答案其实应该是 2 而不是 4。
这道题的难点就在这里：不仅要找能匹配的括号，还要保证它们在地理位置上是连续的。而“连续”这两个字，恰恰是状态设计的一个关键约束。
2.2 一维DP解法的状态设计和转移方程
先说DP思路，因为它对后面理解其他DP题更有迁移价值。
定义dp[i]表示“以第i个字符为结尾的最长有效括号子串的长度”。为什么这样定义？因为“以i结尾”这个约束让状态天然地保留了后缀信息，转移的时候只需要看前一个状态。
分两种情况：
如果s[i]是左括号(，那么以它结尾的有效子串长度必然是 0，因为一个有效括号串不可能以左括号结束。 如果s[i]是右括号)，就要看s[i-1]：
- 当
s[i-1]是左括号时，形式是...()，那么dp[i] = dp[i-2] + 2。这里的dp[i-2]表示这对括号前面的那段有效长度，如果 i<2 就按 0 处理。 - 当
s[i-1]也是右括号时，说明s[i]需要和更前面的某个左括号配对。这个左括号的位置是i - dp[i-1] - 1。如果这个位置存在且是左括号，那么dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2]。最后加上的dp[i - dp[i-1] - 2]表示“这对括号的前面还能拼接上的有效长度”，这一步非常容易漏掉。
上面这段逻辑我建议多读几遍。dp[i-1]是以i-1结尾的合法长度，i - dp[i-1] - 1就是要找的配对位置。如果在配对位置左边还有一段已经合法的子串，也要拼进来，因为这个子串和当前这对括号是连续的。
2.3 关键代码与边界处理
def longestValidParentheses(s: str) -> int: n = len(s) if n < 2: return 0 dp = [0] * n ans = 0 for i in range(1, n): if s[i] == '(': continue if s[i-1] == '(': dp[i] = (dp[i-2] if i >= 2 else 0) + 2 else: # s[i-1] == ')' j = i - dp[i-1] - 1 if j >= 0 and s[j] == '(': dp[i] = dp[i-1] + 2 + (dp[j-1] if j >= 1 else 0) ans = max(ans, dp[i]) return ans边界处理上有三个容易出错的地方：
第一，dp[i-2]在下标越界时要返回 0。第二，j = i - dp[i-1] - 1可能等于 -1，说明i-1之前的有效长度已经把整个前缀都覆盖了，这时找不到配对位置。第三，dp[j-1]同样可能越界，需要判断。
我在自己写第一遍时就在第二点上栽了跟头，写成if j >= 0 and s[j] == '('之后仍然报错，后来才意识到dp[j-1]还要单独判断。建议你在本地测试时重点跑这几个用例："()"、")()"、"(()"、"()()"，这几个用例能把所有边界都覆盖到。
2.4 另一种思路：栈解法里藏着什么
用栈解这道题也很经典，而且代码更短、更不容易出错。
栈里存的是“下标”，初始时压入 -1，作为开始位置的哨兵。遍历字符串，遇到(就把下标压入栈；遇到)就弹出栈顶，然后判断：
- 如果弹出后栈为空，说明这个右括号没有匹配到左括号，那以它为分隔点，把当前下标压入栈，作为新的起始基准。
- 如果弹出后栈不为空，说明从当前栈顶元素的下一个位置到当前位置
i这段是有效括号串，长度等于i - stack[-1]，用它更新答案。
这里“为什么初始要压入 -1”是最容易困惑的地方。其实它是一个虚拟的“左边界”，作用是简化计算：当第一个字符就是右括号且栈内没有任何左括号下标时，弹出 -1 后栈为空，此时把i压栈作为新的基准，之后遇到匹配的右括号，i - stack[-1]才能正确算出长度。
def longestValidParentheses(s: str) -> int: stack = [-1] ans = 0 for i, ch in enumerate(s): if ch == '(': stack.append(i) else: stack.pop() if not stack: stack.append(i) else: ans = max(ans, i - stack[-1]) return ans对比两种解法，DP方法更体现“状态转移”的思想，而栈方法更依赖“括号匹配”的几何直觉。我个人的建议是都掌握，因为面试官可能会让你用一种方法实现，然后追问另一种方法的时间空间复杂度，甚至会引申到“如何处理带通配符的括号匹配”之类的问题。
3. 力扣62：不同路径，从二维DP到组合数学
3.1 为什么这题适合理解DP表的含义
这道题描述很简单：一个m x n的网格，机器人从左上角出发，每次只能向右或向下走一步，问到达右下角有多少条不同路径。
拿到这种题，先别急着写递归。先画一个 3 乘 3 的网格，手动推出每个格子的路径数：第一行全是 1，因为只能一直向右；第一列全是 1，因为只能一直向下；中间格子的路径数等于左边格子的路径数加上边格子的路径数。这就是这张DP表最直观的来源。
更进一步的观察是：到达(i, j)的路径，要么来自(i-1, j)向下走一步，要么来自(i, j-1)向右走一步。因为路径不允许后退，所以这两种来源不会重叠，直接相加即可。这个“来源相加”的过程，本质上就是状态转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]。
3.2 二维DP的写法和空间优化
二维状态最直观的写法是这样：
def uniquePaths(m: int, n: int) -> int: 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]这里初始化时把第一行和第一列都设为 1，省去了单独写边界转移的麻烦。这是二维网格DP里一个非常常用的技巧。
优化成滚动数组的写法也很简单，只需要把二维数组压缩成一维，每次循环里复用：
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-1] return dp[n-1]这里dp[j]在更新之前表示上一行的值，更新之后表示当前行的值。dp[j-1]因为在本次循环的左侧，已经是当前行更新后的值了。这正好对应了dp[i][j] = dp[i-1][j] + dp[i][j-1]。很多人在这个优化这里转不过弯，其实关键就是“一维数组滚动使用时，未被覆盖的值是上一行，已经被覆盖的值是当前行”。
3.3 组合数学解法和溢出问题的提醒
这道题还有另一种思路：机器人从左上到右下，总共要走m-1步向下、n-1步向右，一共m+n-2步。路径数量就等价于在m+n-2步中挑出m-1步向下的组合数，即C(m+n-2, m-1)。
组合数学解法的代码很短：
import math def uniquePaths(m: int, n: int) -> int: return math.comb(m + n - 2, m - 1)这里有一个实际刷题中需要注意的问题：如果你手动实现组合数的阶乘计算，中间结果可能非常大。虽然 Python 的整数没有溢出问题，但如果你用 C++ 或 Java，需要用 long long 并且最好边乘边除，避免溢出。
另外要提醒的是，这道题的数值会随 m、n 增大迅速膨胀。题目中 m、n 不超过 100，最多是C(198, 99)级别，这个数已经很大了，但 Python 的 int 可以轻松处理。如果你用其他语言，建议先估算一下结果范围。
3.4 这道题能扩展出来的面试变形
不同路径最常考的变形有两个。
一个是“网格中有障碍物”，也就是力扣63题，转移时遇到障碍物直接置 0 即可。这个变形考的是“有没有真正理解状态定义”，因为障碍物格子的路径数必须是 0，而且第一行和第一列的初始化处理也从全 1 变成了“碰到障碍物之前为 1，之后为 0”。
另一个是“输出路径本身而不只是数量”，这时需要额外维护一个方向表或者倒推递归，面试中偶尔会出现。你如果能把这两道变形题也做了，对网格DP的掌握会更深一层。
4. 力扣64：最小路径和，初始化处理是最大陷阱
4.1 从“计数”到“最优值”，DP思维的转变
最小路径和和不同路径长得很像，都是m x n网格中从左上角到右下角，但不同之处在于每个格子上有数字，路径代价是经过所有格子的数字之和，要求最小和。
这里思维上最大的转变是：不再求“有几条路”，而是求“哪条路的代价最小”。对应到DP转移方程，就不再是相加，而是dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])。
为什么取 min 而不是同时考虑两条来源？因为到达(i,j)的上一步只有两个方向，而“最小路径和”这个最优子结构要求整个路径的最小代价，所以每一步都取上一个状态的最小值即可。
这道题的代码主体很简单，真正的坑在第一行和第一列的初始化上。很多人直接照着不同路径的写法，把第一行和第一列都初始化为grid[0][0]，结果答案完全不对。原因是第一行只能从左边累加过来，第一列只能从上边累加过来，它们的值应该是前缀和而不是同一个常数。
def minPathSum(grid) -> int: if not grid or not grid[0]: return 0 m, n = len(grid), len(grid[0]) dp = [[0] * n for _ in range(m)] dp[0][0] = grid[0][0] for j in range(1, n): dp[0][j] = dp[0][j-1] + grid[0][j] for i in range(1, m): dp[i][0] = dp[i-1][0] + grid[i][0] for i in range(1, m): for j in range(1, n): dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]) return dp[m-1][n-1]如果不想开二维数组，可以在原数组上直接原地修改，也就是把grid[i][j]本身当作 DP 表来用。这样做的好处是不用额外空间，缺点是会破坏原数据。面试时我一般会问一句“能否原地修改原数组”，如果允许，原地写法最简洁。
4.2 滚动数组版本里有两个同步更新的细节
把最小路径和改造成一维滚动数组时，比不同路径要复杂一点，因为存在“第一列需要单独累加”的问题。参考写法如下：
def minPathSum(grid) -> int: if not grid or not grid[0]: return 0 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] = grid[i][j] + min(dp[j], dp[j-1]) return dp[n-1]注意看两个地方：第一，进入新一行时，dp[0]要先累加当前行的第一列值，这其实就是“第一列只能从上边来”的压缩写法。第二，内层循环里dp[j]在min(dp[j], dp[j-1])中，dp[j]是上一行同列的值，dp[j-1]已经被更新为当前行的左侧值，正好对应min(dp[i-1][j], dp[i][j-1])。
这个同步更新问题是滚动数组里最容易写错的地方。我的建议是：每写完一个滚动数组版本，都用一个小例子比如 2 乘 3 的网格手动跑一遍，确认每个dp[j]的更新时机都符合预期。别嫌麻烦，这一步能帮你避免大量隐性问题。
4.3 变形题的扩展思路
最小路径和最常见的扩展是“求最大路径和”，把min改成max就行，但要注意题目是否允许经过负数。如果网格里有负数，单纯求最大路径和就不能简单用贪心，必须保留DP的思路。
另一种扩展是“需要同时记录路径”，这时你要额外开一个pre[i][j]数组，记录(i,j)是从哪个方向来的。最后从终点倒推回去就能还原整条路径。这个扩展考的是“最优解的构造过程”，很多人能算出最优值，却不知道怎么把路径打印出来，建议你顺手写一遍。
5. 三题横向对比：状态定义、空间复杂度与核心坑点
5.1 用一张表看清三题的差异
| 题目 | 维度 | 目标 | 状态定义 | 转移方程 | 空间优化 |
|---|---|---|---|---|---|
| 32 最长有效括号 | 一维字符串 | 最长长度 | dp[i]以 i 结尾的最长有效括号长度 | 按s[i-1]分两种来源 | 常数空间也可做 |
| 62 不同路径 | 二维网格 | 方案总数 | dp[i][j]到 (i,j) 的路径数 | dp[i][j] = dp[i-1][j] + dp[i][j-1] | 一维滚动数组 |
| 64 最小路径和 | 二维网格 | 最小代价 | dp[i][j]到 (i,j) 的最小路径和 | dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]) | 一维滚动数组或原地修改 |
这张表是整个文章的浓缩版。你可以发现，网格类的两题在状态定义上几乎一样，区别只在第一行第一列的处理和转移方程中的运算方式。而32题作为一维DP，难点在于状态不是简单的前一个位置，而是要借dp[i-1]跳到更远的位置去配对。
5.2 三题的常见错误和排查思路
先说32题。最常见错误是在第二种情况里漏加dp[j-1]，导致类似"()(())"这样的用例答案少算。排查办法是准备几个拼接型用例，例如"()()"、"(())"、"()(())"，确保每段有效括号拼接后的长度能正确累计。
再说62题。最常见错误是m和n搞反，或者dp数组的维度写错。排查办法是用m=1或n=1的边界用例，如果答案不是 1，说明行列写反了。
最后说64题。最常见错误是初始化第一行第一列时没有做累加，而是全部赋成grid[0][0]，结果导致路径和比预期小很多。排查办法是构造一个 2 乘 2 的网格，手算一遍再和程序输出对比，基本几秒钟就能发现问题。
我在这些题目上反复栽过跟头，所以特别建议你给自己准备一份“三题易错点清单”，二刷前先过一遍，能大大节省复习时间。
6. 刷题中的实操心得与排查技巧
6.1 如何利用这些题建立DP题感
我个人的体会是，刷DP题不要追求数量，而是要追求“看见题目就能判断状态设计方向”的能力。这三道题恰好能训练三种判断：看到字符串上的”连续“要求，就想到以字符结尾定义状态；看到网格上的“只能向右向下”，就想到二维DP表；看到“最小/最大/方案数”这些关键词，就想到取min、max或累加的转移操作。
建议你按这个顺序练习：先挣扎 15 分钟自己思考，想不出来再看题解，然后关掉题解重新写一遍。写完之后不要急着下一题，花 5 分钟用一句话总结“这道题的状态是什么、转移为什么这么写”，写在笔记里。
6.2 编译运行之外，还有三个细节值得注意
第一，务必测试空输入和单元素输入。比如s=""、m=1,n=1、grid=[[5]]，这些用例能验证代码的鲁棒性。第二，注意数据规模对结果的影响。不同路径在m=100,n=100时结果会比较大，如果你用 C++，提前开long long。第三，如果是面试手写代码，主动和面试官确认“是否可以原地修改输入数组”，这既展示了你的沟通意识，也能帮你选择更合适的实现方式。
6.3 刷完这三题后，可以继续进阶的方向
如果这三道题你已经能轻松做到一遍通过，下一步可以刷这几道关联题目：力扣5（最长回文子串），它和32题同样是“以某个位置为结尾”的区间DP思路；力扣63（不同路径II），体会障碍物如何影响状态转移；力扣120（三角形最小路径和），这是二维DP向三角形结构的自然延伸；力扣221（最大正方形），它需要你把DP状态从路径长度扩展成边长。
从这三道题出发，动归的知识树会逐渐铺开。但不管刷到哪里，再回头看看这三道题，你会发现它们几乎包含了网格DP最高频的所有考点：初始化、边界、滚动数组、最优子结构。把它们吃透，这笔账绝对不亏。
对我个人来说，最大的收获不是记住了代码模板，而是理解了状态定义的重要性——一个清晰的状态定义，往往比复杂的优化技巧更能决定一道题的成败。希望我踩过的这些坑、总结的这些对比，能帮你在刷这三道题时省下一些本来会浪费在调试上的时间。
