区间DP 模板总结（递推版 / 记忆化搜索版通用伪代码）-平芜编程栈

区间 DP（interval DP）的核心，就是“状态 = 一个区间”，“转移 = 把区间拆成左右两个子区间再合并结果”。oi-wiki+1
下面用模板化的方式讲一遍：什么时候想到区间 DP、怎么设计状态与转移，以及常见两种代码写法（递推版 / 记忆化搜索版伪代码）。cnblogs+1

典型特征与建模套路

区间 DP 适用的一般特征：dotcpp+1

问题在一个序列上，要求的是“某一段连续子区间”的最优值（最大 / 最小 / 方案数等）。
能把一个区间 [l,r][l,r][l,r] 的决策拆成“枚举中间断点 kkk”，再由两边子区间 [l,k][l,k][l,k]、[k+1,r][k+1,r][k+1,r] 的答案合并得到 [l,r][l,r][l,r] 的答案。
子区间必须是连续的，且大区间必然由更小区间组合而成。

常见例子：石子合并、矩阵链乘、戳气球、回文子串分割等，本质上都是“枚举断点拆区间 + 合并子问题”。csdn+1

抽象模型（极其常用的那种）：oi-wiki+2

状态：

dp[l][r]dp[l][r]dp[l][r]：表示处理区间 [l,r][l,r][l,r] 时的最优值。

转移：

在区间 [l,r][l,r][l,r] 内枚举一个“分割点” kkk，把区间拆成两部分：[l,k][l,k][l,k]、[k+1,r][k+1,r][k+1,r]。
然后用某个“合并代价 / 合并收益”把两边结果加在一起：
例如：

dp[l][r]=min⁡l≤k<r{dp[l][k]+dp[k+1][r]+mergeCost(l,r,k)}dp[l][r] = \min_{l \le k < r} \{dp[l][k] + dp[k+1][r] + \text{mergeCost}(l,r,k)\}dp[l][r]=l≤k<rmin{dp[l][k]+dp[k+1][r]+mergeCost(l,r,k)}

边界：

通常长度为 1 的区间（单个元素）容易直接给出：如合并代价 0、收益等。

枚举顺序：

必须保证在计算 [l,r][l,r][l,r] 之前，所有更短的子区间已经计算过。

递推版通用伪代码模板（长度枚举）

这是最常见、最标准的区间 DP 写法，用“区间长度从小到大”的顺序枚举：csdn+2

// n 个元素，下标 1..n // dp[l][r]：区间 [l, r] 的最优值 // 初始化 for l in 1..n: dp[l][l] = base_value_of_single(l) // 视题目而定，例如 0 或 a[l] 等 // 区间长度从 2 开始（至少两个元素才需要合并） for len in 2..n: // len = 区间长度 for l in 1..n-len+1: // 枚举左端点 r = l + len - 1 // 确定右端点 dp[l][r] = +INF or -INF or 0 // 根据是求最小 / 最大 / 计数初始化 // 在 [l, r-1] 枚举分割点 k for k in l..r-1: // 左右子区间 [l, k], [k+1, r] 一定已经被算过 candidate = dp[l][k] + dp[k+1][r] + merge_cost(l, r, k) dp[l][r] = better(dp[l][r], candidate) answer = dp[1][n]

说明要点：dotcpp+1

外层 len 从小到大，保证用到的子区间都是“长度更短”的。
中间 l 枚举左端点，r 由 len 推出。
最内层 k 是断点，一般是 l…r-1。

merge_cost(l,r,k) 根据题目不同，可能是：

区间权值和，如石子合并用前缀和 sum[r] - sum[l-1]。csdn+1
与元素值相关的乘积等，如戳气球那种 a[l-1]*a[k]*a[r+1]。csdn

better() 是 min / max 或 “加法 + 取模”等，视题目目标而定。

如果是“最大值 DP”，只需把初始化和 better 换成对应的最大化即可，例如：dp[l][r] = -INF; dp[l][r] = max(dp[l][r], candidate)。csdn+1

记忆化搜索版通用伪代码模板（递归写法）

同一个思想可以写成递归 + 记忆化（有时思路更直观）：cnblogs+1

// n 个元素，下标 1..n // dp[l][r]：区间 [l, r] 的最优值，初值为 UNKNOWN (例如用 -1 或特定 flag 表示未计算) function solve(l, r): if l == r: return base_value_of_single(l) // 区间长度 1 的边界 if dp[l][r] is not UNKNOWN: return dp[l][r] best = +INF or -INF or 0 // 初始化 for k in l..r-1: // 枚举分割点 left = solve(l, k) right = solve(k+1, r) candidate = left + right + merge_cost(l, r, k) best = better(best, candidate) dp[l][r] = best return best answer = solve(1, n)

说明要点：cnblogs+1

递归深度为 O(n)O(n)O(n)，调用次数为 O(n2)O(n^2)O(n2)，每次枚举 O(n)O(n)O(n) 个断点，总复杂度仍然是 O(n3)O(n^3)O(n3)（和递推版同级）。
思维过程上更贴近“把大区间拆成左右两个子区间”的问题分析方式。

模板中常见的细节与变形

1. 初始化与无效值

若求最小值：

dp[l][r] 初始化为一个足够大的数（如 INF）；better 用 min。dotcpp+1

若求最大值：

dp[l][r] 初始化为一个足够小的数（如 -INF）；better 用 max。csdn+1

若是计数型（方案数）：

一般初始化为 0，然后累加方案数。

2. 环形区间（例如环形石子合并）

常见套路：把序列复制一遍，变成长度 2n2n2n 的线性序列，然后在所有长度为 nnn 的区间里取最优值即可。dotcpp+1

伪代码骨架（求某种最优值）：csdn+1

// 将 a[1..n] 复制到 a[n+1..2n] for i in 1..n: a[i + n] = a[i] // 按照普通区间 DP 在 1..2n 上做 for each valid len, l, r in [1..2n]: // 同前面模板计算 dp[l][r] // 最终答案是在所有长为 n 的区间中取最优 ans = +INF or -INF for l in 1..n: r = l + n - 1 ans = better(ans, dp[l][r])

这里的内部转移依旧是标准区间 DP 模板，只是定义的有效区间范围变成了 [1…2n]。dotcpp+1