C++ 区间 DP_c++ 区间dp

区间DP 简介：

        正所谓区间 DP ，就是在区间上进行 DP 。区间 DP 以区间的长度划分阶段，记录两个端点的坐标，通过合并小区间的最优解来求出大区间的最优解。

        在一般的 区间 DP 题目中，区间 DP 的转移依赖于枚举分割点，由此，一般的区间 DP 的时间复杂度为 O() 。

一维区间 DP： 

        一维区间 DP 又被称为普通的区间 DP 。顾名思义，就是在一维的数组上进行区间 DP。其中，最典型的例子就是 石子合并。

        题目大意：

        n 堆石子摆成一个环，每次选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。求：将 n 堆石子合并成 1 堆的最小得分和最大得分。

        解题思路：

        区间 DP 的经典题目，所以当然是用区间 DP 了。先考虑最小的分：先假设石子的摆放并不是环形，而是一条直线。首先，会想到要将第 l 堆石子和第 r 堆石子合并就要先将第 l ~ r 堆石子全部合并：设  为合并第 l ~ r 堆石子的最小的得分，假设区间 [ l ~ r