区间上的动态规划

阅读量：

知识点

一 . 区间DP

区间DP是线性DP的一种具体形式，其以区间长度作为动态规划的阶段划分依据，同时将区间的左右端点作为状态的两个维度。通常情况下，某一状态会由包含于其中且规模更小的区间状态进行转移。阶段（即长度）、状态（即左右端点）以及决策这三个要素，按照由外至内的顺序构成三层循环结构。

一般解法

dp[i][j]用于表示从i到j这一区间范围内的最优解
通过依次从小到大计算所有区间的最优解来实现目标，具体操作是按从小到大的顺序遍历区间长度以及左端点
这构成了区间DP最基本的特点或处理方式。

还存在一种较为特殊的处理方法：

将区间i到j通过k划分为两个子区间，再基于这两个子区间的最优解来求得整体的最优解。这种方法本质上也是对问题进行划分和解决的常见策略。

一 . 环形区间合并问题

在一个环形运动场的周边位置分布着 N 个石子堆，现在需要按照一定顺序将这些石子堆依次合并为一个整体。根据规则，每次操作只能选取两个相邻的石子堆进行合并，形成一个新的石子堆，并将该次合并所得到的石子总数作为得分。

请设计一种算法，用

还没有任何评论哟~