1. 从“数组区间”说起动态规划最容易被低估的一类题型刷算法题刷到一定阶段你会发现一个很有意思的现象很多人背包问题写得飞起股票买卖系列也能默写但一碰到“数组区间”类的动态规划就卡壳。不是不会写状态转移而是压根想不到状态该怎么定义。我自己当年也是这样LeetCode 上区间 DP 的题单前前后后刷了三遍第一遍基本靠看题解第二遍能独立写出七成第三遍才真正摸到这类题的“套路感”。所谓“数组区间”类动态规划核心特征其实就一句话状态定义在数组的某个连续子区间上通过枚举分割点或端点来转移。听起来很抽象但拆开看无非就是几种固定模式——区间长度从小到大递推、左右端点双指针式扩展、前缀和预处理加速区间求和。这些模式一旦吃透你会发现它们之间是相通的甚至很多题只是换了个壳。这篇文章我打算把数组区间 DP 的几类典型问题彻底拆一遍从状态定义怎么想、转移方程怎么推、边界怎么处理到代码怎么写、坑怎么避全部用我自己的理解讲清楚。适合已经会写基础 DP、但在区间类问题上总是找不到感觉的朋友。如果你连 01 背包都还没写利索建议先把线性 DP 和背包过一遍再来看这篇不然可能会有点吃力。2. 数组区间 DP 的核心思路与方案选型2.1 为什么区间 DP 的状态定义总是让人摸不着头脑线性 DP 的状态通常很直观比如dp[i]表示前 i 个元素的最优解dp[i][j]表示走到格子 (i,j) 的最优解。但区间 DP 不一样它的状态往往定义成dp[i][j]表示区间[i, j]上的最优解然后通过枚举一个分割点 k把大区间拆成两个小区间来转移。这个思路的来源其实是分治。你想一个区间[i, j]上的问题如果它能被拆成[i, k]和[k1, j]两个子问题并且子问题的最优解能组合出原问题的最优解那这不就是典型的区间 DP 吗关键在于不是所有区间问题都满足最优子结构所以识别题型的第一步就是判断大区间的解能不能由小区间的解拼出来。我个人的经验是看到以下几种描述基本可以往区间 DP 上靠问题涉及“连续子数组”或“子串”且要求最优值最大/最小/最长/最短操作具有“合并”性质比如把两个相邻区间合并成一个需要枚举一个“分割点”或“断点”来划分区间回文、括号匹配、石子合并这类经典场景反过来说如果问题只涉及前缀或后缀那大概率是线性 DP如果涉及两个字符串的匹配那可能是双序列 DP。区间 DP 的辨识度其实挺高的只是很多人第一次见的时候没建立起这个分类意识。2.2 区间 DP 的两种主流写法递推与记忆化搜索写区间 DP 有两种常见方式一种是按区间长度从小到大递推另一种是记忆化搜索。两种写法各有优劣我分别说一下。递推写法的核心是三层循环第一层枚举区间长度 len第二层枚举左端点 i第三层枚举分割点 k。为什么长度要放在最外层因为区间 DP 的转移依赖比当前区间更短的子区间只有按长度从小到大算才能保证用到的子区间已经计算完毕。这个顺序千万不能搞反我见过太多人把左端点放最外层结果转移时用到了还没算的子区间答案直接错。记忆化搜索则是写一个递归函数solve(i, j)如果dp[i][j]已经算过就直接返回否则枚举分割点递归求解。这种写法的好处是思路直观不用操心遍历顺序坏处是递归深度可能很大而且常数比递推大。对于区间 DP 来说如果区间长度能到几千递归可能会爆栈这时候就得老老实实写递推。我的建议是先用记忆化搜索把逻辑理清楚确认转移方程没问题后再改写成递推版本。这样既保证了正确性又能兼顾效率。下面用一个经典例子来说明两种写法的差异。假设我们要解决“最长回文子序列”问题给定字符串 s求最长回文子序列的长度。状态定义dp[i][j]为 s[i..j] 中最长回文子序列长度。转移方程如果s[i] s[j]则dp[i][j] dp[i1][j-1] 2否则dp[i][j] max(dp[i1][j], dp[i][j-1])记忆化搜索版本写起来很自然def longestPalindromeSubseq(s): n len(s) memo [[-1] * n for _ in range(n)] def solve(i, j): if i j: return 0 if i j: return 1 if memo[i][j] ! -1: return memo[i][j] if s[i] s[j]: memo[i][j] solve(i 1, j - 1) 2 else: memo[i][j] max(solve(i 1, j), solve(i, j - 1)) return memo[i][j] return solve(0, n - 1)递推版本则需要按长度遍历def longestPalindromeSubseq(s): n len(s) dp [[0] * n for _ in range(n)] for i in range(n): dp[i][i] 1 for length in range(2, n 1): for i in range(n - length 1): j i length - 1 if s[i] s[j]: dp[i][j] dp[i 1][j - 1] 2 if length 2 else 2 else: dp[i][j] max(dp[i 1][j], dp[i][j - 1]) return dp[0][n - 1]注意递推版本里length 2时dp[i1][j-1]会越界所以需要特判。这种边界处理是区间 DP 里最容易出错的地方后面我会专门讲。2.3 什么时候该用前缀和优化区间 DP有一类区间 DP 问题转移时需要快速求某个区间的和比如“石子合并”问题中要计算[i, j]区间内石子的总重量。如果每次转移都循环求和时间复杂度会多一个 O(n)整体变成 O(n^4)基本没法接受。这时候前缀和就派上用场了。预处理一个前缀和数组pre[i]表示前 i 个元素的和那么区间[i, j]的和就是pre[j1] - pre[i]O(1) 就能算出来。这样整体复杂度降到 O(n^3)对于 n 在几百以内的题目完全够用。我自己的习惯是只要区间 DP 的转移方程里出现了“区间和”或“区间最值”这类需要聚合的量第一反应就是能不能用前缀和或 ST 表预处理。这个意识建立起来之后很多题的优化就是顺手的事。3. 核心细节解析与实操要点3.1 状态定义的三种常见模式区间 DP 的状态定义虽然灵活但归纳下来无非三种模式我分别用例子说明。模式一dp[i][j]表示区间[i, j]的最优解。这是最基础的定义适用于大多数区间 DP 问题。比如“最长回文子序列”“石子合并”“戳气球”都是这种。转移时枚举分割点 k把[i, j]拆成[i, k]和[k1, j]或者拆成[i, k-1]和[k1, j]加上 k 本身的贡献。模式二dp[i][j]表示以 i 开头、j 结尾的子数组是否满足某性质。这种定义常见于回文类问题比如“最长回文子串”中dp[i][j]表示 s[i..j] 是否是回文。转移时看s[i] s[j]且dp[i1][j-1]是否为真。这种布尔型状态的定义往往比数值型更直观。模式三dp[i][j]表示区间[i, j]被某种操作处理后的结果。比如“移除盒子”问题中dp[i][j][k]表示区间[i, j]在左边有 k 个与 s[i] 相同颜色的盒子时的最大得分。这种三维状态是区间 DP 的进阶玩法维度增加通常是因为需要记录额外的上下文信息。我个人的经验是先尝试模式一如果发现转移时信息不够用再考虑加维度或换定义。不要一上来就想复杂的状态那样容易把自己绕进去。3.2 边界条件的处理区间 DP 最容易翻车的地方区间 DP 的边界处理比线性 DP 复杂得多因为涉及两个端点各种越界情况都要考虑。我总结了几条实战经验第一长度为 1 的区间要单独初始化。比如dp[i][i]通常有明确含义回文问题里是 1石子合并里是 0戳气球里可能是某个基础值。这个初始化不能省否则递推时用到的子区间是未定义值。第二长度为 2 的区间要小心dp[i1][j-1]越界。当j i 1时i1 j-1这个子区间是空的。空区间的值应该定义成什么取决于问题本身。回文问题里空区间长度为 0石子合并里空区间和为 0。我一般会在代码里加一个判断或者把 dp 数组多开一行一列来避免越界。第三枚举分割点时注意 k 的范围。如果转移是dp[i][k] dp[k1][j]那 k 从 i 到 j-1如果是dp[i][k-1] dp[k1][j] cost那 k 从 i 到 j。这个范围搞错的话要么漏解要么越界。提示写区间 DP 时建议先把 dp 数组的维度多开 1 到 2 个单位把边界情况统一处理成 0 或特定值这样能省掉很多 if 判断。3.3 遍历顺序为什么长度必须放在最外层这个问题值得单独拿出来说因为我见过太多人在这里栽跟头。区间 DP 的转移依赖比当前区间更短的子区间所以计算顺序必须保证短区间先算长区间后算。假设我们用dp[i][j]表示区间[i, j]的解转移时用到dp[i1][j]、dp[i][j-1]、dp[i1][j-1]这些。这些子区间的长度分别是j-i、j-i、j-i-1都比j-i1小。所以只要按长度从小到大遍历就能保证用到的子区间已经算好。如果按左端点 i 从 0 到 n-1、右端点 j 从 i 到 n-1 遍历呢当计算dp[i][j]时dp[i1][j]的左端点是 i1比 i 大还没算到dp[i][j-1]的右端点是 j-1虽然比 j 小但左端点还是 i如果内层循环 j 是从小到大那dp[i][j-1]确实算过了。但dp[i1][j]没算所以这种遍历顺序是错的。正确的遍历顺序只有一种外层枚举长度内层枚举左端点。这个顺序没有例外所有区间 DP 都适用。4. 实操过程与核心环节实现4.1 案例一最长回文子序列的完整实现与优化最长回文子序列是区间 DP 的入门题但它的优化空间其实很大。我先给出基础版本再讲空间优化。基础版本就是前面写的 O(n^2) 时间、O(n^2) 空间的递推。这个版本对于 n 在 1000 以内的题目完全够用。但如果 n 到了 5000 甚至更大O(n^2) 的空间就可能超内存这时候需要滚动数组优化。观察转移方程dp[i][j]只依赖dp[i1][j]、dp[i][j-1]、dp[i1][j-1]。如果我们按长度遍历对于固定的长度 len计算dp[i][j]时只需要长度为 len-1 和 len-2 的状态。但问题是dp[i1][j]和dp[i][j-1]都是长度 len-1 的状态它们在同一轮计算中会被覆盖。一种常见的优化方式是只保留两行但区间 DP 的滚动数组比线性 DP 麻烦因为依赖关系是二维的。我个人的做法是如果空间真的紧张就改用记忆化搜索加哈希表存储或者直接用functools.lru_cache让 Python 自己管理内存。实测下来对于 n5000 的回文子序列记忆化搜索配合 lru_cache 能过但速度比递推慢一些。from functools import lru_cache def longestPalindromeSubseq(s): n len(s) lru_cache(maxsizeNone) def solve(i, j): if i j: return 0 if i j: return 1 if s[i] s[j]: return solve(i 1, j - 1) 2 return max(solve(i 1, j), solve(i, j - 1)) return solve(0, n - 1)这个版本代码简洁逻辑清晰适合面试时快速写出。但要注意 Python 的递归深度限制n 很大时需要手动调高sys.setrecursionlimit。4.2 案例二石子合并问题中的前缀和与四边形不等式石子合并是区间 DP 的经典题有 n 堆石子排成一排每次可以合并相邻两堆合并的代价是两堆石子重量之和求合并成一堆的最小总代价。状态定义dp[i][j]为合并[i, j]区间内石子的最小代价。转移方程dp[i][j] min(dp[i][k] dp[k1][j]) sum(i, j)其中sum(i, j)是区间[i, j]的石子总重量用前缀和 O(1) 求出。三层循环时间复杂度 O(n^3)。def stoneMerge(stones): n len(stones) pre [0] * (n 1) for i in range(n): pre[i 1] pre[i] stones[i] def range_sum(i, j): return pre[j 1] - pre[i] dp [[0] * n for _ in range(n)] for length in range(2, n 1): for i in range(n - length 1): j i length - 1 dp[i][j] float(inf) for k in range(i, j): dp[i][j] min(dp[i][j], dp[i][k] dp[k 1][j]) dp[i][j] range_sum(i, j) return dp[0][n - 1]这个 O(n^3) 的版本对于 n100 没问题n1000 就有点悬。进一步优化可以用四边形不等式把内层枚举 k 的范围缩小整体降到 O(n^2)。四边形不等式的结论是如果代价函数满足区间包含单调性和四边形不等式那么最优分割点opt[i][j]满足opt[i][j-1] opt[i][j] opt[i1][j]。利用这个性质内层循环只需要在[opt[i][j-1], opt[i1][j]]范围内枚举。def stoneMergeOptimized(stones): n len(stones) pre [0] * (n 1) for i in range(n): pre[i 1] pre[i] stones[i] dp [[0] * n for _ in range(n)] opt [[0] * n for _ in range(n)] for i in range(n): opt[i][i] i for length in range(2, n 1): for i in range(n - length 1): j i length - 1 dp[i][j] float(inf) for k in range(opt[i][j - 1], opt[i 1][j] 1): val dp[i][k] dp[k 1][j] if val dp[i][j]: dp[i][j] val opt[i][j] k dp[i][j] pre[j 1] - pre[i] return dp[0][n - 1]四边形不等式的证明比较复杂面试时一般不会要求但知道这个优化存在在竞赛或工程中遇到大规模数据时能派上用场。4.3 案例三戳气球的逆向思维与区间划分戳气球这道题很有意思它的难点在于正向思考时戳掉一个气球后左右两边会变成相邻状态不好定义。正确的思路是逆向思考把“戳气球”看成“最后戳某个气球”这样它的左右两边就是独立的子区间。状态定义dp[i][j]为戳破开区间(i, j)内所有气球能获得的最大硬币数。注意这里是开区间i 和 j 是边界不戳。转移时枚举最后戳破的气球 kdp[i][j] max(dp[i][k] dp[k][j] nums[i] * nums[k] * nums[j])其中 k 从 i1 到 j-1。最终答案是dp[0][n1]其中我们在原数组两端各加一个虚拟气球值为 1。def maxCoins(nums): nums [1] nums [1] n len(nums) dp [[0] * n for _ in range(n)] for length in range(2, n): for i in range(n - length): j i length for k in range(i 1, j): dp[i][j] max(dp[i][j], dp[i][k] dp[k][j] nums[i] * nums[k] * nums[j]) return dp[0][n - 1]这道题的关键在于开区间的定义和逆向思维。我当初做这道题时正向想了很久都没想通看了题解才恍然大悟。后来总结出一个经验当正向操作会改变区间结构时试试逆向思考把“第一个操作”换成“最后一个操作”。这个思路在区间 DP 里非常常见。4.4 案例四移除盒子与三维区间 DP移除盒子是区间 DP 的进阶题状态需要三维。题目大意是给定一排盒子每个盒子有颜色每次可以移除连续 k 个同色盒子得分 k^2求最大得分。这道题的难点在于移除中间某段后两边的同色盒子可能会合并产生额外得分。所以状态需要记录“左边有多少个与当前区间左端点同色的盒子”。状态定义dp[i][j][k]为区间[i, j]左边有 k 个与boxes[i]同色的盒子时的最大得分。转移有两种直接移除boxes[i]及其左边的 k 个同色盒子(k1)^2 dp[i1][j][0]在[i1, j]中找一个 m使得boxes[m] boxes[i]把[i1, m-1]先移除让boxes[i]和boxes[m]合并dp[i1][m-1][0] dp[m][j][k1]def removeBoxes(boxes): n len(boxes) dp [[[0] * n for _ in range(n)] for _ in range(n)] def solve(i, j, k): if i j: return 0 if dp[i][j][k] ! 0: return dp[i][j][k] # 优化合并左边连续同色盒子 while i 1 j and boxes[i 1] boxes[i]: i 1 k 1 res (k 1) * (k 1) solve(i 1, j, 0) for m in range(i 1, j 1): if boxes[m] boxes[i]: res max(res, solve(i 1, m - 1, 0) solve(m, j, k 1)) dp[i][j][k] res return res return solve(0, n - 1, 0)这道题的时间复杂度是 O(n^4)空间 O(n^3)对于 n100 已经是极限。实际写的时候那个 while 循环的优化很关键能把连续同色盒子先合并减少状态数。我第一次写的时候没加这个优化直接超时后来加上才过。5. 常见问题与排查技巧实录5.1 区间 DP 调试速查表问题现象可能原因排查方法答案偏小分割点枚举范围漏了边界检查 k 的范围是否覆盖 i 到 j-1 或 i 到 j答案偏大区间和重复计算检查前缀和是否用对区间和是否只加了一次数组越界长度为 2 时dp[i1][j-1]越界特判 length2或 dp 数组多开一维结果不稳定遍历顺序错误确认长度在最外层左端点在内层超时缺少前缀和或四边形不等式优化检查转移中是否有可预处理的区间聚合量递归爆栈记忆化搜索深度过大改用递推或调高递归深度限制5.2 我踩过的三个典型坑坑一把长度循环和左端点循环写反了。这个错误我犯过不止一次尤其是在手写代码的时候。有一次面试题目是“最长回文子串”我信心满满地写完结果跑出来答案是错的。检查了半天才发现我把for i in range(n)放在了外层for length in range(2, n1)放在了内层。这样计算dp[i][j]时dp[i1][j-1]还没算用的是初始值 0。改过来之后立刻正确。这个教训让我养成了一个习惯写完区间 DP 后先手动模拟一遍长度为 2 和长度为 3 的情况确认遍历顺序没问题。坑二忘记处理空区间。在“戳气球”问题中dp[i][j]定义在开区间上当j i 1时区间内没有气球应该返回 0。我一开始没注意这个边界导致dp[i][i1]的值是未初始化的最终答案偏小。后来在代码里加了一句if j - i 1: return 0才解决。空区间的处理在区间 DP 里非常普遍建议在写转移之前先把所有可能的空区间和单元素区间的值明确下来。坑三前缀和数组下标偏移。前缀和pre[i]表示前 i 个元素的和那么区间[i, j]的和是pre[j1] - pre[i]。这个j1很容易写成j导致区间和少算一个元素。我在“石子合并”里就犯过这个错答案总是比正确答案小一点。排查的时候我打印了每个区间的和和暴力计算的结果对比才发现是下标偏移。建议写前缀和的时候先写一个暴力版本验证确认无误后再替换。5.3 区间 DP 的复杂度分析与优化方向区间 DP 的基础复杂度是 O(n^3)三层循环分别是长度、左端点、分割点。空间复杂度 O(n^2)。对于 n 在 500 以内的题目这个复杂度基本能过。如果 n 到了 1000 以上就需要优化。优化方向主要有三个第一前缀和预处理。把区间求和从 O(n) 降到 O(1)这是最基础的优化几乎所有区间 DP 都要做。第二四边形不等式。把分割点枚举范围从 O(n) 降到 O(1) 均摊整体复杂度降到 O(n^2)。适用条件是代价函数满足区间包含单调性和四边形不等式。常见的石子合并、邮局问题都满足。第三状态压缩。如果状态只依赖相邻长度可以用滚动数组把空间降到 O(n)。但区间 DP 的滚动数组比较麻烦因为依赖关系是二维的实际用得不多。我个人的建议是先把 O(n^3) 的版本写对再根据数据范围决定要不要优化。不要一上来就追求最优解那样容易在细节上出错。5.4 如何判断一道题是不是区间 DP最后分享一个我自己的判断流程遇到新题时按这个顺序过一遍问题是否涉及连续子数组或子串如果是进入下一步。是否要求最优值最大/最小/最长/最短如果是进入下一步。大区间的解能否由小区间的解组合得到如果是进入下一步。是否需要枚举分割点或端点来划分区间如果是基本可以确定是区间 DP。如果第 3 步不满足那可能是贪心或线性 DP。如果第 4 步不满足那可能是双指针或滑动窗口。这个判断流程不是绝对的但能覆盖大部分情况。另外区间 DP 和双序列 DP 容易混淆。双序列 DP 的状态通常是dp[i][j]表示第一个序列前 i 个和第二个序列前 j 个的匹配情况转移时看s[i]和t[j]的关系。区间 DP 的状态是同一个序列上的两个端点。区分方法很简单看状态的两个维度是不是在同一个序列上。如果是就是区间 DP如果不是就是双序列 DP。我在实际刷题中发现区间 DP 的题目数量其实不多但每道题都有独特的思考角度。把最长回文子序列、石子合并、戳气球、移除盒子这四道题吃透基本就能覆盖 80% 的区间 DP 场景。剩下的就是在这四道题的基础上做变形比如加个限制条件、改个代价函数、换个状态定义。万变不离其宗核心还是那套“枚举分割点、按长度递推”的框架。