区间DP的特征: 可以两个或多个部分进行整合, 或者反过来；能将问题分解为能两两合并的形式.
区间DP的求解: 对整个问题设最优值，枚举合并点，将问题分解为左右两个部分，最后合并两个部分的最优值得到原问题的最优值。
一般的方法是枚举长度(最外层L, 0 < L < N), 枚举左端点(第二层i, 0 < i < N-L), 以此可确定右端点(j = i + L), 枚举合并点 (i <= t < j).
什么是枚举合并点? 好比我要在一块蛋糕的第i厘米到第j厘米直接切一刀, 可以切在哪里? 在i~j之间下的那一刀就是合并点, 需要一个loop来枚举.
石子合并
设有N堆石子排成一排，其编号为1，2，3，…，N。
每堆石子有一定的质量，可以用一个整数来描述，现在要将这N堆石子合并成为一堆。
每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。
例如有4堆石子分别为 1 3 5 2， 我们可以先合并1、2堆，代价为4，得到4 5 2， 又合并 1，2堆，代价为9，得到9 2 ，再合并得到11，总代价为4+9+11=24；
如果第二步是先合并2，3堆，则代价为7，得到4 7，最后一次合并代价为11，总代价为4+7+11=22。
- 思路
经典区间DP. 二维得相当标准.
这题会很容易记忆, 因为子问题是"合并第i个物体到第j个物体的最优解", 而原问题则是 "已合并第1个物体到第N个物体的最优解".
class Solution{
public int mergeStones(int[] a){
int[] arr = new int [a.length+1];
int N = a.length;
for(int i = 1;i <= N;i++){
arr[i] += a[i-1];
}
for(int i = 1;i <= N;i++){
arr[i] += arr[i-1];
}
//prefix sum
int [][] dp = new int [N+1][N+1];
for(int l = 2;l <= N;l++){ //枚举区间长度 - i到j之间的距离
for(int i = 1;i + l <= N+ 1;i++){ //枚举左端点
int j = i + l -1;
dp[i][j] = Integer.MAX_VALUE;
for(int k = i;k<j;k++){ //k是合并点, 此处枚举合并点, 从i到j之间都要考虑.
dp[i][j] = Math.min(dp[i][j], dp[i][k]+dp[k+1][j]+(arr[j] - arr[i-1]));
}
}
}
return dp[1][N];
}
}
Minimum Cost to Merge Stones
这道题给了我们N堆石头，每堆石头有不同的个数，说每次可以合并K堆石头，合并堆的花费就是石头的个数，然后问如何合并，才能使总花费最小。然后给了一些例子，通过观察例子，可以发现，并不是所有的输入都能成功合成一堆，比如例子2，无论先和并哪三堆，最终都会剩下两堆，从而无法进一步合并，因为 K=3，每次至少需要合并三堆。我们当然希望能在开始合并之前就能知道最终是否能成功合并为一堆，而不是算到最后了才发现白忙了一场，所以要来分析一下，什么时候才能最终合并为一堆。再来看看例子2，每次要将三堆合并为一堆，那么就是减少了两堆，而要使得最终能够剩下一堆，其他的都要合并调，假设原来共有n堆，只能剩下一堆，就是说 n-1 堆都要减掉，而每次只能减少 k-1 堆，所以只要 n-1 能够整除 k-1即可，即 (n-1)%(k-1) == 0 成立，这样就可以提前判断了。
好，接下来继续，考虑如何来解题，首先要意识到这道题的情况可能非常多，用暴力搜索的话可能会非常的复杂，而且当前的合并方法完全会影响到之后的合并，所以基本是要放弃 Brute force 的想法的。同样，这道题也不能用贪婪算法，每次都合并石子个数最少的三堆会收敛到局部峰值，不一定是全局的，所以只能另辟蹊径。观察到这题是玩数组的，又是求极值的题目，那么就要祭出神器动态规划 Dynamic Programming 了，先来考虑定义 dp 数组吧，最简单直接的方法肯定直接用个二维的dp数组了，其中 dp[i][j] 表示合并范围 [i, j] 内的石头堆的最小花费，最终 dp[0][n-1] 就是所要求的值。看到了论坛上有人定义了三维的 dp 数组，把每次合并的堆数K也当作一维放入到 dp 数组中了，其实博主觉得不是很有必要，因为像这种必须要对 dp 数组进行升维操作的是当题目中有隐藏信息 Hidden Information，而当前定义的 dp 数组无法重现子问题，即无法找到状态转移方程的时候必须要做的
根据之前打气球的经验，要从小区间开始更新，多小呢，从K开始，因为小于K的区间不用更新，其 dp 值一定为0，因为每次必须合并K堆石子，所以区间的长度 len 从K遍历到 n。好，区间长度确定了，现在要确定起点了，i从0遍历到 n-len 即可，有了区间的起点和长度，可以确定区间的终点 j = i+len-1。目标就是要更新区间 [i, j] 的dp值，先初始化为整型最大值。接下来的更新方法，即状态转移方程，就是本题最大的难点了，要求区间 [i, j] 的 dp 值，没法直接得到，但是由于是从小区间开始更新的，所以 suppose 其中的小区间的 dp 值都已经更新好了，就可以将大区间拆成两个小区间来更新了。一般来讲，将一个数组拆成两个非空子数组的时候，会遍历其所有情况，比如 [1, 2, 3, 4]，会拆成 [1] 和 [2,3,4]，[1,2] 和 [3,4], [1,2,3] 和 [4]。但是这道题由于其特殊性，并不需要遍历所有的拆分情况，因为某些区间是无法通过合并石子堆得到的，就拿上面的例子来说，若 K=3，那么就不需要用 [1,2] 和 [3,4] 来更新整个区间，它们都不到3个，无法合并，所以遍历的时候每次跳过 K-1 个位置即可，用 t 来分别区间 [i, j]，然后每次 t += K-1 即可，用两个小区间的 dp 值来更新整个区间。这还没有完，当某个子区间正好可以合并为一堆石子的时候，其 dp 值要加上该区间所有的石子数。举个最简单的例子，比如 [1, 2, 3]，K=3，那么我们分割的话，只能用 dp[0] [0]+ dp[1] [2] 来更新 dp[0] [2]，但是 dp[0] [0] 和 dp[1] [2] 均为0，因为区间长度均小于3，那么我们的 dp[0][2] 值就无法更新成正确的值了，这三个数字是可以合并的，所以要加上区间内所有的数字之和，而为了快速的求得任意区间和，采用提前建立累加和数组 sums 的方式，来提高计算效率，所以整个状态转移方程为：
dp[i][j] = min(dp[i][j], dp[i][t] + dp[t + 1][j]); -> (i <= t < j)
dp[i][j] += sums[j + 1] - sums[i]; -> if ((j - i) % (K - 1) == 0)
有了状态转移方程，我们就可以写出代码如下：
class Solution {
public:
int mergeStones(vector<int>& stones, int K) {
int n = stones.size();
if ((n - 1) % (K - 1) != 0) return -1;
vector<int> prefix(n + 1);
for (int i = 1; i <= n; ++i) {
prefix[i] = prefix[i - 1] + stones[i - 1];
}
vector<vector<vector<int>>> f(n, vector<vector<int>>(n, vector<int>(K + 1, 0x3f3f3f3f)));
for (int i = 0; i < n; ++i) {
f[i][i][1] = 0;
}
for (int len = 2; len <= n; ++len) {
for (int i = 0; i <= n - len; ++i) {
int j = i + len - 1;
for (int k = 2; k <= K; ++k) {
for (int m = i; m < j; m += K - 1) {
f[i][j][k] = min(f[i][j][k], f[i][m][1] + f[m + 1][j][k - 1]);
}
}
f[i][j][1] = f[i][j][K] + prefix[j + 1] - prefix[i];
}
}
return f[0][n - 1][1];
}
};