【题解】一本通1274 合并石子

区间dp 的入门题

$dp_{i,j}$ 为 $[i,j]$ 区间中的最小得分

区间dp一般是对于每个区间 $[i,j]$ 枚举一个 $k$ 将区间 $[i,j]$ 切为两端并计算总区间代价

得出转移方程: $dp_{i,j} = min\{dp_{i,k} + dp_{k+1,j} + \sum\limits_{l=i}^{j}arr_l\}$

代码中需要使用前缀和预处理掉方程中的那个 $l$ 省去一个 $n$ 的时间复杂度

最终复杂度 $O(n^3)$

#include <iostream>
#include <cstring>
using namespace std;
int n,arr[110],psum[110],dp[110][110];
int main(){
	memset(dp,0x3f,sizeof(dp));
	cin >> n;
	for(int i=1;i<=n;i++)	cin >> arr[i],psum[i] = psum[i-1] + arr[i],dp[i][i] = 0;
	for(int i=n-1;i>=1;i--)
		for(int j=i+1;j<=n;j++)
			for(int k=i;k<j;k++)
				dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]+psum[j]-psum[i-1]); 
	cout << dp[1][n] << endl;
	return 0;
}