当状态定义不同时，状态转移方程有差别。请思考以下两种状态对应的状态转移方程，并自行推导，锻炼DP分析能力。

第一种：f[L][len] 表示合并起点为 L、长度为 len 的区间的最小代价。代码如下（by ZFJ）：

#include <iostream>
#include<cstring>
using namespace std;

const int N = 310;
int m[N], pre[N];
// f[i][j]：区间长度为i、区间起点为j时的合并代价
int f[N][N];

int main() {
	int n;
	cin >> n;
	memset(f, 0x3f, sizeof f); // 求min，初始化为正无穷，但为了防止溢出，初始化为0x3f
	for (int i = 1; i <= n; i++) {
		cin >> m[i];
		pre[i] = pre[i - 1] + m[i]; // 	前缀和优化后面的多次区间求和
		f[1][i] = 0; // 区间长度为1的dp初始值是0，因为状态转移方程里算过了（前缀和部分）
	}

	for (int len = 2; len <= n; len++) // 状态：区间长度
		for (int L = 1; L <= n - len + 1; L++) { // 枚举区间左端点
			int R = L + len - 1;
			for (int k = 1; k < len; k++) // 枚举区间内断点的【相对】位置
				f[len][L] = min(f[k][L] + f[len - k][L + k] + (pre[R] - pre[L - 1]), f[len][L]);
		}

	cout << f[n][1];

	return 0;
}

第二种：f[L][R] 表示合并得到起点为 L、终点为 R 的区间的最小代价。代码如下（by HYR）：

#include<iostream>
#define inf 0x3fffffff
#define N 400
using namespace std;
int a[N],m[N],f[N][N];
int main(){
	fill(&f[0][0],&f[N-1][N-1],inf);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		m[i]=m[i-1]+a[i];
		f[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++)
				f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+m[j]-m[i-1]);
		}
	cout<<f[1][n];
	return 0;
}

递归

#include<bits/stdc++.h>
using namespace std;
const int N=305;
int n;
int a[N];
int s[N];
int f[N][N];
int get(int l,int r)
{
	return s[r]-s[l-1];
}
int dfs(int l,int r)
{
	if(f[l][r])return f[l][r];
	if(l==r)return 0;
	int mi=0x3fffffff;
	for(int i=l;i<r;i++)
		mi=min(mi,dfs(l,i)+dfs(i+1,r));
	return f[l][r]=mi+get(l,r);
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=n;i++)
		s[i]=s[i-1]+a[i];
	cout<<dfs(1,n);
	return 0;
}