区间动态规划属于线性DP的一种，也称区间DP，以区间长度作为DP的阶段，以区间的左右端点作为状态的维度。一个状态通常由被它包含且比它更小的区间状态转移而来。阶段（长度）、状态（左右端点）、决策三者按照由外到内的顺序构成三层循环。
石子合并
- 直线版石子合并问题石子合并问题--直线版
直线版石子合并，每次合并任意的相邻堆，合并堆的花费为两个堆的石子之和，使合并成一堆的最终的花费最大或最小。
求解过程：dp[i,j]表示区间i到j的最小得分或最大得分，转移方程为：
其中，sum为前缀和。
回文串
- 修改为回文串的最小花费让字符串成为回文串的最少插入次数
修改为回文串的最小花费：求向字符串s中插入字符使之成为回文串的最小操作次数。
求解过程：dp[i,j]表示区间i到j变为回文串所需经过的最新少插入次数，转移方程为：
