Interval DP

释义 Definition

区间动态规划（interval DP）：一种动态规划思路，把问题按“区间 \([l, r]\)”来定义状态并递推，常用于需要在区间内选择分割点或合并顺序的题型（如矩阵连乘、石子合并、回文划分等）。其中 DP 是 dynamic programming（动态规划）的缩写。

发音 Pronunciation (IPA)

/ntrvl dipi/

例句 Examples

We can solve this with interval DP.
我们可以用区间动态规划来解决这个问题。

Using interval DP, we compute \(dp[l][r]\) for all subranges and try every split point \(k\) to minimize the cost.
使用区间动态规划时，我们会计算所有子区间的 \(dp[l][r]\)，并枚举每个分割点 \(k\) 来最小化代价。

词源 Etymology

interval 来自拉丁语 intervallum（意为“间隔、空间”）；DP 是 dynamic programming 的缩写，该术语与方法在 20 世纪由美国数学家 Richard Bellman 推广。interval DP 作为组合用法，多见于算法教学与竞赛语境，用来强调“按区间建模的 DP”。

文学与著作中的用例 Literary Works

Steven Halim 等，《Competitive Programming 3》：在讲解经典区间问题（如矩阵连乘、区间合并类题目）时常用“interval DP/Range DP”的表述与套路总结。
Antti Laaksonen，《Competitive Programmer’s Handbook》：介绍动态规划模式时涵盖“按区间定义状态”的常见做法（与矩阵连乘等经典模型关联）。
Thomas H. Cormen 等，《Introduction to Algorithms（CLRS）》：虽未必频繁直接写“interval DP”这一竞赛术语，但其经典例题 Matrix-Chain Multiplication（矩阵连乘） 是区间 DP 的代表性模型之一。