区间DP：主要处理区间范围上的问题

1. 基本特征：
   状态定义：dp[i][j], i是区间左端点，r是区间右端点
2. 遍历方式：

 // 区间长度从小到大遍历
   for(int len = 2; len <= n; len++) {           // 枚举区间长度len
       for(int i = 1; i <= n-len+1; i++) {       // 枚举左端点i
           int l = i, r = i + len - 1;           // 计算右端点r
           f[l][r] = 1e9 / -1e9;
           for(int k = l; k < r; k++) {          // 枚举分割点k
               dp[l][r] = max/min(dp[l][r], dp[l][k] + dp[k+1][r] + cost);
           }
       }
   }
  cost 实际上就是将最后的两个子区间合并成一个大区间时需要付出的代价`

AC代码块：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 310;
int n;
int a[N];
int f[N][N];

int main()
{
    scanf("%d", &n);

    for (int i = 1; i <= n; i++)  scanf("%d", &a[i]);

    for (int i = 1; i <= n; i++)  a[i] += a[i - 1];  // 前缀和

    for (int len = 2; len <= n; len++) // 枚举区间
    {
        for (int i = 1; i <= n - len + 1; i++) // 枚举左端点
        {
            int l = i, r = i + len - 1; // 生成右端点
            f[l][r] = 1e9;
            for (int k = l; k < r; k++) // 枚举分割点K：左右断点区间进行枚举
            {
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + (a[r] - a[l - 1]));
            }
        }
    }

    printf("%d\n", f[1][n]);

    return 0;
}