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 ]最后一次合并的两区间是 [
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！