区间DP

区间DP

1、石子合并：

​ 每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N 堆石子合并成为一堆。

​ 每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。

​ 问题是：找出一种合理的方法，使总的代价最小，输出最小代价。

思路：

核心思路：从小区间逐步扩展区间，最后得到整个区间的最优解

（1）区间长度从小到大枚举

（2）每种长度都进行所有起点的枚举
（3）将区间(l, r)合并所需要的代价初始化为无穷大
（4）然后对该区间进行状态转移，每次都拿出最后一个状态，进行比较

代码：

for (int i = 1; i <= n; i ++) cin >> s[i];  //读入数组
   for (int i = 1; i <= n; i ++) s[i] += s[i - 1]; //求其前缀和

   for (int len = 2; len <= n; len ++) //枚举长度
       for (int i = 1; i + len - 1 <= n; i ++) //从前到后，枚举不同长度下，给左边区域和右边区域分配不同数量是的代价，求最小值
       {
           int l = i, r = i + len - 1; //以当前位置为左边部分（只有一个数），剩余部分都是右边部分
           f[l][r] = 1e8;  //先将所有从第l堆石子到第r堆石子合并到一堆石子的代价置为无穷
           for (int k = l; k < r; k ++)    //逐渐将右边的数拿给左边求代价，右边至少留一个
               f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
       }

   //所有将第1堆石子到第n堆石子合并的所有方式的代价最小值
   cout << f[1][n] << endl;

核心：

​ 区间合并的问题，通用的一个模板：

for (int len = 1; len <= n; len++) {         // 区间长度
    for (int i = 1; i + len - 1 <= n; i++) { // 枚举起点
        int j = i + len - 1;                 // 区间终点
        if (len == 1) {
            dp[i][j] = 初始值
            continue;
        }

        for (int k = i; k < j; k++) {        // 枚举分割点，构造状态转移方程
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + w[i][j]);
        }
    }
}