线性DP，区间DP

线性DP

就是在线性数据结构上用DP，简称线性DP。
说人话就是用线性数据结构来优化DP。
一般用单调队列或单调栈优化。
单调队列主要用于维护两端指针单调不减的区间最值，而单调栈则主要用于维护前/后第一个大于/小于当前值的数。
其实就是用线性数据结构维护能转移到当前状态的所有数值，每次接近 \(O(1)\) 求出这一段区间的最优解进行转移（一般转移一个区间是 \(O(n^2)\) 的，但是这个复杂度通常不是正解）。

区间DP

线性DP一般设置状态为 \(dp_{i,j}\) 表示在区间 \([1,i]\) 内状态为 \(j\) 的最优解。但是有时候左边界不能只设置为 \(1\)，这时候就要用到区间DP。
区间DP一般设置状态位 \(dp_{i,j}\) 表示在区间 \([i,j]\) 内的最优解，有时候需要加其他的维度限制。这样区间DP的转移至少是 \(O(n^2)\) 的。