区间dp

定义：区间类动态规划是线性动态规划的扩展，它在分阶段地划分问题时，与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来有很大的关系。

令状态 $f(i,j) $表示将下标位置 i 到 j 的所有元素合并能获得的价值的最大值，那么 $f(i,j)=\max{f(i,k)+f(k+1,j)+cost}$，$cost $为将这两组元素合并起来的价值

性质

1. 合并： 即将两个或多个部分进行整合，当然也可以反过来
2. 特征 能将问题分解为能两两合并的形式
3. 求解 对整个问题设最优值，枚举合并点，将问题分解为左右两个部分，最后合并两个部分的最优值得到原问题的最优值

解题模板
区间dp问题枚举时，第一维通常是枚举区间长度，并且一般 len = 1 时用来初始化，枚举从 len = 2 开始；第二维枚举起点 i （右端点 j 自动获得，j = i + len - 1）

模板代码

for (int len = 1; len <= n; len++) {         // 区间长度
    //终止条件代表右端点要小于n
    for (int i = 1; i + len - 1 <= n; i++) { // 枚举起点
        int j = i + len - 1;                 // 区间终点
        if (len == 1) {
            dp[i][j] = 初始值
            continue; //或者在下方加上else
        }

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

石子合并

问题描述：设有 N 堆石子排成一排，其编号为 1,2,3,…,N。每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N堆石子合并成为一堆。
每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。
找出一种合理的方法，使总的代价最小，输出最小代价

状态表示

1. 集合：$ f(i,j) $ 表示将 [i,j] 这段区间的物品合并在一起的方案集合
2. 属性：最小代价
3. 集合划分，最后一次合并一定是左边连续的一部分和右边连续的一部分进行合并，将集合划分成某一堆是由区间 $ [i,i] ，[i,i+1] ，[i,i+2] ，… ， [i,i + j-1] $ 这些情况中之一所合并而成（即所有方案中，最后一次合并时，其中的某一堆一定是由上述某个区间所合并而成，满足不重不漏的原则）
4. 除了最后一次以外前面每次合并的和即为该次合并所产生的代价，因此最小总代价 = $ f(i,k) + f(k+1,j) + s[j] - s[i-1] $
5. $ f(i,j) $

状态计算

1.
2.

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int f[N][N],s[N],n,w[N]; //dp数组；前缀和数组

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> w[i];
    }
    for(int i=1;i<=n;i++){
        s[i] = s[i-1] + w[i];
    }
    memset(f, 0x3f, sizeof f); //由于是求最小值，因此先把dp数组设置成最大值
    // 区间 DP 枚举套路：长度+左端点 
    for(int len=1;len<=n;len++){ //len表示[i, j]的元素个数
        // 右端点j小于0
        for(int i=1;i+len-1<=n;i++){ 
            int j = i+len-1; // 自动得到右端点
            if(len == 1){
                f[i][j] = 0; // 边界初始化
                continue;
            }
            for(int k=i;k<j;k++){
                f[i][j] = min(f[i][j],f[i][k] + f[k+1][j] + s[j] - s[i-1]);
            }
        }
    }

    /*
    for(int len=2;len<=n;len++){
        //右端点j小于0
        for(int i=1;len+i-1 <= n;i++){
            //j-i+1 = len
            int j = len+i-1;
            
            //初始化f[i][j]为一个较大值（题目要求最小代价）
            f[i][j] = 1e9;
            //枚举合并点
            for(int k=i;k<=j-1;k++){
                f[i][j] = min( f[i][j] , f[i][k] + f[k+1][j] + s[j] - s[i-1]);
                // cout << f[i][j] << "\n";
            }
        }
    }    

    */
    cout << f[1][n];
    return 0;
}