刷力扣的人应该都清楚动态规划是绕不过去的一座山。而“力扣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]表示这对括号前面的那段有效长度如果 i2 就按 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步向右一共mn-2步。路径数量就等价于在mn-2步中挑出m-1步向下的组合数即C(mn-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数组的维度写错。排查办法是用m1或n1的边界用例如果答案不是 1说明行列写反了。最后说64题。最常见错误是初始化第一行第一列时没有做累加而是全部赋成grid[0][0]结果导致路径和比预期小很多。排查办法是构造一个 2 乘 2 的网格手算一遍再和程序输出对比基本几秒钟就能发现问题。我在这些题目上反复栽过跟头所以特别建议你给自己准备一份“三题易错点清单”二刷前先过一遍能大大节省复习时间。6. 刷题中的实操心得与排查技巧6.1 如何利用这些题建立DP题感我个人的体会是刷DP题不要追求数量而是要追求“看见题目就能判断状态设计方向”的能力。这三道题恰好能训练三种判断看到字符串上的”连续“要求就想到以字符结尾定义状态看到网格上的“只能向右向下”就想到二维DP表看到“最小/最大/方案数”这些关键词就想到取min、max或累加的转移操作。建议你按这个顺序练习先挣扎 15 分钟自己思考想不出来再看题解然后关掉题解重新写一遍。写完之后不要急着下一题花 5 分钟用一句话总结“这道题的状态是什么、转移为什么这么写”写在笔记里。6.2 编译运行之外还有三个细节值得注意第一务必测试空输入和单元素输入。比如s、m1,n1、grid[[5]]这些用例能验证代码的鲁棒性。第二注意数据规模对结果的影响。不同路径在m100,n100时结果会比较大如果你用 C提前开long long。第三如果是面试手写代码主动和面试官确认“是否可以原地修改输入数组”这既展示了你的沟通意识也能帮你选择更合适的实现方式。6.3 刷完这三题后可以继续进阶的方向如果这三道题你已经能轻松做到一遍通过下一步可以刷这几道关联题目力扣5最长回文子串它和32题同样是“以某个位置为结尾”的区间DP思路力扣63不同路径II体会障碍物如何影响状态转移力扣120三角形最小路径和这是二维DP向三角形结构的自然延伸力扣221最大正方形它需要你把DP状态从路径长度扩展成边长。从这三道题出发动归的知识树会逐渐铺开。但不管刷到哪里再回头看看这三道题你会发现它们几乎包含了网格DP最高频的所有考点初始化、边界、滚动数组、最优子结构。把它们吃透这笔账绝对不亏。对我个人来说最大的收获不是记住了代码模板而是理解了状态定义的重要性——一个清晰的状态定义往往比复杂的优化技巧更能决定一道题的成败。希望我踩过的这些坑、总结的这些对比能帮你在刷这三道题时省下一些本来会浪费在调试上的时间。