刷题刷到动态规划这块的朋友应该都绕不开这三道经典题力扣32“最长有效括号”、62“不同路径”、64“最小路径和”。很多人刷力扣是按题号顺序来的但我觉得这三道题放在一起看更有意思——它们分别代表了动态规划里三个不同层次的模型一维状态推导、二维状态表格、带权路径决策。从32到64难度不是线性上升的而是思维方式的切换。我先把话放这儿如果你只打算背模板三道题都能背下来但换个变形题照样懵如果你把这三种DP模型吃透了后面再刷一堆中等难度的题都会觉得顺手很多。这三道题表面上一个处理括号字符串一个处理网格路径一个处理矩阵最小代价本质上都在问同一个问题当前状态怎么从之前的状态转移过来。区别在于32要处理“括号匹配的连续性”62要处理“路径来源的叠加”64要在叠加之外再考虑“最小代价选择”。理解了它们的共性和差异你等于同时复习了动态规划的三块核心基石。我自己刷这三题的时候用一句话总结就是32考的是DP数组的“下标语义”62考的是DP表格的“初始化”64考的是“边界的最后一公里”。这三关你能打通动态规划的基本功就算站稳了。1. 三道题放在一起看到底在考什么很多人刷题有个误区喜欢一道一道地刷刷完就忘。我建议换个思路按模型归类。32、62、64这三道题就是非常好的归组样本。1.1 从题目描述看它们的表面差异先来快速回顾一下三道题都说了什么。力扣32“最长有效括号”给你一个只包含(和)的字符串找出最长有效格式正确且连续括号子串的长度。经典例子是(()返回2())返回2()(()返回2而(()())返回6。力扣62“不同路径”一个机器人位于m x n网格的左上角每次只能向下或向右移动一步问到达右下角总共有多少条不同路径。比如3 x 2的网格答案是37 x 3的网格答案是28。力扣64“最小路径和”给定一个包含非负整数的m x n网格找出一条从左上角到右下角的路径使得路径上的数字总和最小每次同样只能向下或向右移动。一个经典测试用例是grid [[1,3,1],[1,5,1],[4,2,1]]最小路径和是7。这三道题如果用暴力法统统不可行。32的暴力枚举子串要O(n²)甚至O(n³)62和64的暴力DFS直接指数爆炸。所以它们天然是算法题不是考你写代码而是考你怎么建模。1.2 表面不同本质同一状态转移思维我在刷题时习惯先问一个问题如果我知道了所有“更小规模”的答案能不能拼出“当前规模”的答案32里如果我知道了以s[i-1]结尾的最长有效括号长度能不能推出以s[i]结尾的长度答案是能但要分情况讨论。62里如果我知道了到达(i-1, j)的路径数和到达(i, j-1)的路径数到达(i, j)的路径数就是两者之和。因为最后一步不是从上面来就是从左边来。64里如果我知道了到达(i-1, j)的最小路径和和到达(i, j-1)的最小路径和到达(i, j)的最小路径和就是“较小者 当前格子的值”。因为要保证总和最小最后一步肯定选择代价更小的那个来源。看三句话结构完全一样。这就是动态规划的核心思考方式——把大问题拆成“最后一步 之前子问题”。你一旦习惯了这种提问方式看到新题的第一反应就不会是“怎么枚举”而是“最后一步是什么之前的子问题是什么”。提示判断一道题能不能用DP可以先问自己——“如果我算出了所有更小规模的最优解能否在常数时间内组合出当前规模的最优解”能则DP不能大概率要换搜索或贪心思路。1.3 从难度梯度看动态规划的成长路径说实话如果按代码量排62和64的代码比32还短。但按思维量排32反而是最绕的。我的看法是62是“入门”它让你理解DP表是怎么填的64是“进阶”它让你理解初始化和边界的坑32是“攻坚”它让你理解DP下标的设计可能比状态转移本身更烧脑。所以我把这三道题当成一套组合拳先用62建立“表格感”再用64强化“边界感”最后用32提升“下标感”。刷完之后你对动态规划的二维表格和一维滚动数组都会有比较深的肌肉记忆。2. 力扣32最长有效括号——最绕的下标设计这道题我第一次刷的时候翻车了看题解都看晕了因为网上给的解法有两种栈和动态规划。我后来是先把栈的解法弄懂再切换到DP才彻底理解下标语义。2.1 栈解法括号配对最直觉的写法用栈解括号匹配是经典中的经典但这里有个细节和普通的括号匹配不一样我们找的是“连续有效括号子串”所以不能只消消乐还得记录“从哪里开始断了”。栈里不存字符而是存下标。这样每次遇到右括号能把栈顶弹出来然后通过i - stack.peek() - 1或者i - stack[stack.length - 1]算出当前有效子串长度。具体步骤我直接给出来初始化一个栈栈底提前放一个-1这个很关键后面说。从左到右遍历字符串下标记为i。遇到(把i压入栈。遇到)先弹出一个元素即匹配掉一个左括号如果栈顶是左括号下标的话就算栈顶是别的也该弹因为我们要重新计算起点。弹出后如果栈不为空说明当前右括号找到了匹配对象计算i - 栈顶元素更新最大长度如果栈为空说明这个右括号是多余的它不能和任何左括号匹配于是把i压入栈作为新的“起点基准”。这个“起点基准”就是栈底那个-1的升级版。为什么要放-1因为如果整个字符串从第一个字符开始就有效比如()遍历到下标1时弹出左括号下标0栈里还剩-1那么1 - (-1) 2长度就是2。如果栈底不提前放-1这一步就算不出长度了。放上完整代码Python版力扣支持的语言无所谓思路一致def longestValidParentheses(s: str) - int: stack [-1] # 栈底基准下标 max_len 0 for i, ch in enumerate(s): if ch (: stack.append(i) else: stack.pop() if stack: max_len max(max_len, i - stack[-1]) else: stack.append(i) # 多余右括号重置基准 return max_len这个解法的时间复杂度O(n)空间复杂度O(n)。思路很好懂也足够AC。2.2 动态规划解法状态转移方程里藏着两个分支但是如果你只会栈解法我只能说这道题你掌握了一半。DP解法才是真正锻炼思维的地方。DP思路是这样的定义dp[i]表示以s[i]结尾的最长有效括号长度。注意这个**“以s[i]结尾”非常关键**它限定了我们只统计连续且有效的子串。然后分情况讨论情况一s[i] (那dp[i] 0。因为以左括号结尾的子串不可能有效肯定长度为0。这没什么好说的。情况二s[i] )再分两个分支分支As[i-1] (也就是形如...()此时dp[i] dp[i-2] 2。因为()本身贡献2再加上()前面那个连续有效子串的长度dp[i-2]。举例(()())计算下标5时s[4](所以dp[5] dp[5-2] 2 dp[3] 2 2 2 4。分支Bs[i-1] )也就是形如...))此时要考虑是否有一个左括号能和当前右括号匹配。这个左括号应该位于i - dp[i-1] - 1的位置也就是“以 s[i-1] 结尾的有效子串再往前一个字符”。如果这个位置存在且是(那么匹配成功dp[i] dp[i-1] 2 dp[i - dp[i-1] - 2]。这里最后再加dp[i - dp[i-1] - 2]是因为匹配成功后当前子串前面可能还接着另一个有效子串要连起来。举例()(())计算下标5时s[4])dp[4] 2所以i - dp[i-1] - 1 5 - 2 - 1 2s[2](匹配成功dp[5] dp[4] 2 dp[2 - 1] 2 2 dp[1] 2 2 0 4。这个分支B的转移方程是这道题最劝退的地方。很多人就是在这里绕晕的。我画个图来理解一下下标: 0 1 2 3 4 5 字符: ( ) ( ( ) ) dp: 0 2 0 0 2 4计算dp[5]时s[5])s[4])所以要看i - dp[i-1] - 1 5 - 2 - 1 2这个位置s[2](匹配成功。此时dp[5] dp[4] 2 dp[1]其中dp[1] 2表示最前面的()。合起来整个字符串() (())长度为 4正确。代码实现如下def longestValidParentheses(s: str) - int: dp [0] * len(s) max_len 0 for i in range(1, len(s)): if s[i] ): 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) max_len max(max_len, dp[i]) return max_len注意边界i-2可能越界j-1也可能越界都要加保护判断。我有一个习惯写DP的转移方程时先写无边界条件的版本再分别在每个数组下标访问的地方补if ... else这样可以避免漏掉边界。2.3 为什么推荐两种解法都掌握栈解法的优势是直观不用琢磨复杂的转移方程DP解法的优势是逻辑完整能帮你建立“以某位置结尾”的DP思维框架。两种都能AC但在面试场景下如果面试官追问“这个状态到底代表什么”你能随时说出dp[i]的语义比背代码强得多。我实际刷题的经验是先用栈AC一道题再用DP重新AC一遍这个方法对动态规划入门特别有效。同样的题目两种思路互相对照比刷十道新题都管用。而且力扣的讨论区里32题最有价值的不是代码而是那些配着图解释分支B的手绘图我建议刷到这题的朋友别急着看代码先在草稿纸上按上面的方法画一遍。注意这道题的DP里dp[i]表示“以i结尾的最长有效括号长度”而题目的答案是max(dp)不是dp[-1]。因为最长有效子串不一定在字符串末尾。这个“遍历过程中不断取max”的模式在很多DP题里通用。3. 力扣62不同路径——最经典的二维DP表格相比32的下标烧脑62就友好多了。它是标准的二维DP入门题非常适合建立表格感。3.1 状态定义和转移方程一次讲透定义dp[i][j]为“从左上角到达(i, j)的路径数”。机器人每次只能向下或向右所以到达(i, j)只有两种可能从上方(i-1, j)走下来从左侧(i, j-1)走过来因此dp[i][j] dp[i-1][j] dp[i][j-1]。这个方程简单到让人想笑但它的推导过程是动态规划的核心范式。写出来def uniquePaths(m: int, n: int) - int: # dp[i][j] 表示从起点到 (i, j) 的路径数 dp [[0] * n for _ in range(m)] # 第一行和第一列都只有一条路径 for j in range(n): dp[0][j] 1 for i in range(m): dp[i][0] 1 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.2 初始化细节第一行和第一列的“唯一路径”为什么是1很多人写二维DP时会忽略初始化直接套转移方程结果数组越界或者答案全是0。这里的关键是dp[0][j]和dp[i][0]没有“上方”或“左侧”它们只能沿着边界一直走所以路径数恒为1。比如说3行7列的网格第一行的所有格子都只能“一直向右走”到达所以每个格子路径数都是1第一列同理。如果你不从这些格子开始填表内层循环到i0或j0时就会访问越界下标。还有个小细节整个dp数组的初始化值是多少不重要反正会被覆盖但建议统一初始化为0。因为dp[0][0]实际上是起点本身从左到右从下到上都不需要经过什么路径它本身就代表“1种方式”因为机器人在起点时不需要移动就已经在起点。把dp[0][0]直接设为1也可以但需要确保第一行第一列的循环逻辑一致否则会重复赋值。3.3 空间压缩一维数组滚动更新的原理与写法62题还有个大名鼎鼎的优化技巧滚动数组能把空间复杂度从O(m×n)压缩到O(n)。原理是dp[i][j]只依赖上一行的dp[i-1][j]和当前行的dp[i][j-1]所以只要保留一行数据从左到右原地更新即可。def uniquePaths(m: int, n: int) - int: dp [1] * n for _ in range(1, m): for j in range(1, n): dp[j] dp[j] dp[j-1] return dp[n-1]这段代码的精髓在于dp[j]在更新前存的是上一行的值dp[i-1][j]dp[j-1]在当前行已经更新成dp[i][j-1]了两者相加正好是dp[i][j]。很多初学者觉得这写法神乎其神其实就是“当行从左到右滚动覆盖”。提示我用一个生活类比帮你记——这就像一个走廊里有一排计数器每到一个格子你把当前计数器的旧值加上左边计数器的新值得到当前格子应该有的值。走到走廊尽头这一排计数器正好变成了新的一行的数据。62题的变体很多比如有障碍物的63不同路径II、带权重的后续题等。你把62的空间压缩写法吃透之后64题最小路径和也用得上。4. 力扣64最小路径和——在路径数量上叠加代价如果说62是“数路”64就是“选路”。同样是二维网格同样是只能向右向下但这次每个格子有个权值你要找一条总和最小的路径。62的转移是加法64的转移是取最小值再加当前值。4.1 状态转移方程取小者再加当前格值定义dp[i][j]为“从起点到达(i, j)的最小路径和”。要到达(i, j)只有两个来源上面的(i-1, j)和左边的(i, j-1)。为了让总和最小当然选这两个来源里更小的一种然后加上当前格子的值dp[i][j] min(dp[i-1][j], dp[i][j-1]) grid[i][j]没错就这么简单。代码def minPathSum(grid: List[List[int]]) - int: 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] min(dp[i-1][j], dp[i][j-1]) grid[i][j] return dp[m-1][n-1]4.2 和62的对比同样是二维DP差别在哪里62和64代码结构几乎一样只是dp[i][j]的计算方式从变成了min 。但这里有个非常关键的差异值得单独拎出来讲初始化不是全1而是累加前缀和。62的第一行和第一列路径数全是1因为一到边界就只有直线这一种走法。但64的第一行和第一列是“沿着边界一直走的代价累加”因为边界上没有选择从起点到某个边界格子的路径是唯一的代价就是一路上所有格子值的和。这个差异是64题最容易错的地方。有个同学问过我“为什么第一行不能每个都是grid[0][j]”我反问他“你从起点走到(0, 2)难道不经过(0, 1)吗经过的话代价为什么不加”他一拍大腿就明白了。边界上的路径是“唯一确定的路线”代价必须连续累加。如果你只写grid[0][j]等于跳过了中间的格子答案肯定错。4.3 原地修改技巧能否直接改原数组有没有可能不用额外dp数组可以。如果你不介意修改原数组直接在grid上操作就行因为每个格子只被读一次改完也不会影响后续计算。这样空间复杂度降到O(1)def minPathSum(grid: List[List[int]]) - int: m, n len(grid), len(grid[0]) for i in range(m): for j in range(n): if i 0 and j 0: continue elif i 0: grid[i][j] grid[i][j-1] elif j 0: grid[i][j] grid[i-1][j] else: grid[i][j] min(grid[i-1][j], grid[i][j-1]) return grid[m-1][n-1]这段代码连额外空间都省了但是有两个前提一是你不在原数组上做别的用途二是你清楚地知道自己在修改原数据。我个人的习惯是刷题阶段宁可多开一个dp数组可读性优先如果面试官明确要求O(1)空间再展示原地修改。写代码是给人看的不是给自己炫技的。5. 三道题横向对比从状态定义到代码结构的异同这三道题刷完之后我建议你停下来做一个对比表格把它们放在一起看比单独刷十道题更有收获。5.1 状态定义、转移方程、初始化、遍历顺序对比题目状态定义转移方程初始化遍历顺序32dp[i]以s[i]结尾的最长有效括号长度s[i](时0s[i])且s[i-1](时dp[i-2]2s[i-1])且ji-dp[i-1]-1处是(时dp[i-1]2dp[j-1]dp[0]0其余为0从左到右62dp[i][j]到达(i,j)的路径数dp[i][j] dp[i-1][j] dp[i][j-1]第一行第一列全为1逐行逐列64dp[i][j]到达(i,j)的最小路径和dp[i][j] min(dp[i-1][j], dp[i][j-1]) grid[i][j]dp[0][0]grid[0][0]第一行第一列为累加和逐行逐列从这个表能看出什么32是一维DP62和64是二维DP32和62的状态转移都不涉及“代价选择”只有64涉及“取min”。这意味着32和62更偏向“计数型DP”64是“最优型DP”。5.2 为什么62和64的遍历顺序是从上到下、从左到右很多初学者看到二维DP的循环嵌套就直接抄不知道为什么。其实原因很简单当前格子的值依赖上方和左方的值所以必须保证计算(i,j)前(i-1,j)和(i,j-1)都已经算好了。逐行从上到下、行内从左到右天然满足这个依赖关系。换个角度验证如果你从右往左填一行那么算(i,j)时左边的(i,j-1)还没算结果就是错的。这个“依赖方向决定遍历方向”的规律在DP里是通吃的。如果你遇到一个问题发现状态依赖右边和下面那就得换遍历方向比如从右下往左上填。5.3 空间压缩技巧是否是通用的62的空间压缩滚动数组完全可以搬到64上因为64同样只依赖上一行和当前行左边的值def minPathSum_rolled(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[n-1]这里的细节是外层循环进入新一行时dp[j]存的是上一行的值dp[i-1][j]dp[j-1]存的是当前行已经更新的值dp[i][j-1]所以直接min(dp[j], dp[j-1]) grid[i][j]就是正确的当前格值。这个“上一行遗留 当前行新算”的思维是滚动数组的核心。6. 实操中的常见问题与排查心得刷这三道题我遇到过的典型问题不少。整理一份问题清单和排查方法给你。6.1 力扣32容易踩的空和边界问题32的DP解法里最容易错的点有两个一是dp[i-2]可能越界当i1时二是分支B里j i - dp[i-1] - 1可能是负数。我建议你在写代码之前先把i0和i1这两种情况在纸上演算一遍确认循环从i1开始是安全的然后所有越界访问都加上判断。栈解法也有坑如果输入是空字符串栈初始[-1]不弹出max_len为0正确如果输入全是右括号比如)))每次遇到右括号都会弹出、栈空、把当前下标压入最后max_len还是0正确。这个行为恰好验证了“多余右括号重置基准”的设计。6.2 力扣62容易忽视的整数溢出问题62的答案会随m和n快速增大。比如m10, n10时答案是48620但m23, n12时答案已经到193536720超过2亿。力扣的约束是1 m, n 100当m100, n100时答案远超32位整数的上限。如果你用的语言默认int是32位这里就会溢出。我建议在 Python 里不用担心但在 C/Java 里要记得用long或long long。如果面试时被问到这个细节你主动提一句“这个值可能超出32位范围我需要用更大的整数类型”会显得很有经验。6.3 力扣64的初始化顺序和“先填边界还是先填整体”之争64题初始化容易糊涂的是dp[0][0]到底要不要单独处理。我的写法是先单独给dp[0][0] grid[0][0]然后第一行从j1开始累加第一列从i1开始累加最后主循环从i1, j1开始。这种“先把边界煮熟再煮内部”的思路很直观。但也有一些题解会把所有格子放在一个双重循环里用if-elif-else判断来源像我上面展示的原地修改写法那样。两种写法都能AC但维护性和可读性差别很大。我个人偏好“显式初始化边界”因为边界上的语义就是和其他位置不同写成独立的循环一目了然。6.4 调试DP表格的实战方法打印二维数组这三道题特别是62和64如果你答案不对我最推荐的调试方法不是看变量而是把dp数组打印出来。你可以写一个简单的辅助函数def print_dp(dp): for row in dp: print(row)然后在关键循环结束之后打印一次。比如62题你跑一个3x3的输入打印结果应该是[1, 1, 1] [1, 2, 3] [1, 3, 6]如果看到某一行不对马上就能定位是初始化问题还是转移方程写错。很多问题你看代码半天看不出来表格一打印毛病立刻现行。这个方法对任何二维DP都适用包括64。6.5 刷题顺序的心得为什么先62再64再32我的刷题顺序建议是62 - 64 - 32。先62是因为它最纯粹没有任何弯弯绕就是让新手第一次体验“填DP表”的感觉。64在62基础上加了“取min”让你体会“最优型DP”和“计数型DP”的区别。32放到最后因为它的一维DP其实比二维DP更难想象特别是分支B的回溯索引需要你脑子里能画出一个括号子串的“边界位置图”。反过来如果你先刷32很容易被劝退产生“DP太难了”的错觉。实际上不是DP难是32的边界情况多。用难度梯度喂自己才是刷题的正确打开方式。7. 一套通用的动态规划审题方法说了这么多具体题目最后送你一套通用的DP审题方法。这是我刷了几百题之后总结出来的遇到新题直接用7.1 四步审题法状态、转移、初始化、答案第一步定状态。问自己要找的答案能不能用“某个位置/某个元素结尾/到达”来描述能就把这个描述写成dp[i]或dp[i][j]。第二步写转移。问自己当前状态能不能由“前一个/上边/左边的状态”推出把这个关系写成方程。第三步定初始化。问自己最小的子问题是什么边界位置的值是多少这一步最容易错把所有数组越界位置都在草稿纸上标出来。第四步想答案。问自己题目要的最终结果等于哪个状态结尾的dp[n-1]不一定是对的可能要遍历取max如32题可能要取表格右下角如62、64。这个方法不能保证你解出所有DP题但能保证你不至于拿到题后一脸懵。至少你能快速判断出“这道题合不合适用DP”。7.2 从这三道题延伸出去的变体题目刷完32、62、64我建议你接着刷这几道题巩固力扣63不同路径II62的变体网格里有障碍物转移时跳过障碍即可力扣70爬楼梯和32一样是一维DP只不过转移非常简单力扣120三角形最小路径和64的变体状态转移略复杂力扣279完全平方数一维DP求最小数量你会发现这些题的本质都逃不出前面总结的框架。所谓“刷题攻略”不是让你背题解而是让你积累足够多的“模型”看到新题时能快速匹配到已有模型并做出微调。就拿63来说62的dp[i][j] dp[i-1][j] dp[i][j-1]需要加一个条件如果(i,j)是障碍dp[i][j] 0。这就是“计数型DP遇到障碍怎么处理”的通用套路你在62上理解了表格在63上就不会慌。8. 最后再分享一点刷题心态这三道题我前前后后刷了不止五遍每次重刷都有新体会。第一遍刷32的时候我连题目都看不懂什么叫“有效括号子串”都理解了半天后来刷到64还因为dp[0][0]初始化错误卡了半小时。但正是这些卡壳让我现在看到同类题能一眼看穿状态定义和转移方向。如果你现在觉得DP很难我给你一个定心丸DP的难是“门内难”不是“门外难”。就是说你只要推开第一道门把62这种最基础的表格题搞明白后面64、32甚至更难的题都是在这个基础上叠加条件而已。不怕慢就怕不总结。每次刷完题花十分钟把状态定义、转移方程、初始化、遍历顺序四个方面写下来比多刷十道题都值。说实话力扣上很多人是把这三道题当成“经典题”背下来的但我更希望你能把这三题当成“模型题”来理解。背下来的是别人的经验理解了的才是自己的判断力。动态规划的核心从来不是代码技巧而是思维习惯看到问题先想“最后一步是什么之前的状态怎么组合”——这个习惯一旦养成你刷题的后半程会越走越顺。按我自己的进度从这三道题出发大概两周就能把一维DP和二维DP的主要变体摸熟。希望这篇拆解能帮你少走一点弯路。刷题没有捷径但有地图——62、64、32就是这张地图上最清楚的三个地标。