动态规划经典题目（一）：石子合并

This blog post is only available in Simplified Chinse.

动态规划（Dynamic Programming），简称DP，是用于求解决策过程中的最优化数学方法，不仅用于编程领域，也用于管理学、经济学、生物学（具体这三个地方怎么用就不关我们事了）。作为NOIP竞赛的每年必考题型，动态规划是很重要的！！！

石子合并（NOI1995）（区间DP）

洛谷题目提交网址：石子合并

在一个圆形操场的四周摆放N堆石子，现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数记为该次合并的得分。试设计出一个算法，计算出将N堆石子合并成1堆的最小得分和最大得分。

输入第一行为 n（n≤100），表示有 n 堆石子。第二行为 n 个用空格隔开的整数，依次表示这 n 堆石子的石子数量。（ ≤1000）

输出共 2 行；第 1 行为将 n 堆石子合并成一堆的最小得分；第 2 行为将 n 堆石子合并成一堆的最大得分。

3
1 2 3

9
11

一看到这题，我第一个想到的就是合并果子这道题。这两题的确很像，但是仔细看就发现他们存在的很明显的一个不同是：这题只能合并相邻两堆，而合并果子那题可以随便跳两堆合并。那么这题可以用贪心吗？显然有很多很多很多的反例，以求最小为例，比如有六堆石子，分别是3 4 6 5 4 2：

贪心：3 4 6 5 4 2
5 4 6 5 4 (+5)
9 6 5 4 (+9)
9 6 9 (+9)
15 9 (+15)
24 (+24)
Total：62

正解：3 4 6 5 4 2
7 6 5 4 2 (+7)
7 6 5 6 (+6)
7 6 11 (+11)
13 11 (+11)
24 (+24)
Total：59

所以贪心的方法肯定是不行的。再回来看看这题，发现首先决策不是按照一堆一堆来的，也就是说没法刷线性的DP；一个决策可以划分成很多子决策（也就是说所有的合并可以是1~i的合并得分+i+1~n的合并得分），那么不显然是区间DP嘛！

首先处理环的问题。一般处理环的问题的方法就是：复制一份，放到序列尾，这样就把环变成长度为原来两倍的链了。例如：

环：1 2 3 4
链：1 2 3 4 1 2 3 4

接下来，DP正式部分：定义F[i][j]为从i到j一段石子合并的最优解。那么自然会想到在i～j-1之间枚举k（为什么是j-1不是j？看转移方程就知道了），为了方便我们先造出前缀和sum，转移方程：

F[i][j]=max/min(F[i][k],F[k+1][j])+sum[j]-sum[i-1];

复杂度：O(N³)。

算是挺简单的一题。