题解 区间dp

更好的阅读体验
想看AC代码的请直接划至最低端。

---

什么是区间dp？
区间dp就是在区间上进行动态规划，求解一段区间上的最优解；该问题的求解思路主要是通过合并小区间的最优解进而得出整个大区间上最优解的dp算法。（实际上还是通过子问题的解来求出原问题的解）

核心思路
既然需要求解一个区间上的最优解，那么我们把这个区间分割成一个个小区间，求解每个小区间的最优解，再合并小区间得到大区间即可。
所以在代码实现上，我们可以枚举区间长度 len 为每次分割成的小区间长度，再在内层枚举该小区间的起点，自然终点也就可以通过起点和len求出了。然后在这个起点终点之间枚举分割点，求解这段小区间在某个分割点下的最优解。

题目分析
这显然是一道区间dp的模板题。
这是 状态转移方程 :
$dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]+s[j]-s[i-1])$
$dp[i][j]$ 指的是从 $i$ 到 $j$ 的区间的最优解
$s$ 指的是存储大区间上数字的前缀和数组（因此在输入后要进行前缀和处理）
$dp[i][k]+dp[k+1][j]$ 分割点 $k$ 前的小区间的最优解加分割点 $k$ 后的小区间的最优解

再来看看伪代码：

//代码实现
//初始化 (dp[i][i] = 0 只有一个数字，无需合并 )
for(/*列举区间长度*/){ 
     for(/*列举左端点的位置*/){ 
          int j = ? ; //尾的位置
          for(/*分割点的位置*/){ 
              /*状态转移方程*/
          }
     }
}

好了，自己再去写写，等会再往下看吧

---

欢迎回来！
AC代码：

#include<iostream>
#include<cstring>
using namespace std;
int a[305],s[305],dp[305][305];
int n,ans;
int main(){
    cin >> n;
    for(int i = 1;i <= n;i++){
        cin >> a[i];
    }
    for(int i = 1;i <= n;i++){
        s[i] = a[i] + s[i-1]; //前缀和处理
   }
   memset(dp,0x3f,sizeof(dp));
    for(int i = 1;i <= n;i++){
        dp[i][i] = 0;  //初始化
    }
    for(int len = 2;len <= n;len++){ //列举区间长度
        for(int i = 1;i+len-1 <= n;i++){ //头的位置
            int j = i+len-1; //尾的位置
            for(int k = i;k < j;k++){ //分割点的位置
               dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]+s[j]-s[i-1]);
            }
        }
    }
    cout << dp[1][n]; //答案就是1到n的大区间的最优解
    return 0;
}