顾名思义，区间DP便是在区间上做DP （废话）。区间DP的主要思想现在小区间上做DP得到最优解，通过把小区间的答案合并来得到大区间的最优解，最终得到整个区间的答案。
区间DP的计算量比较大。一个长度为 \(n\) 的区间，编程时，区间DP至少需要两层 \(for\) 循环，第1层的 \(i\) 从区间的首部或尾部开始；第2层的 \(j\) 从 \(i\) 开始到 \(n\) 结束，\(i\) 和 \(j\) 一起枚举所有的子区间。所以，区间DP的复杂度大于 \(O(n^2)\) 一般为 \(O(n^3)\)。