题解 | #最优二叉树II#

区间dp： dp[l][r][0]表示区间l~r作为左子树的最小开销

dp[l][r][1]表示区间l~r作为右子树的最小开销

对于区间[l][r]枚举根节点k，分别计算l~r作为左子树和作为右子树的最小代价

在l~r区间上，以k为根的树作为左子树的代价可以计算为val[k]*val[r+1]+dp[l][k-1][0]+dp[k+1][r][1]。

同理，作为右子树的代价可以计算为dp[l][r][1]=min(dp[l][r][1],val[k]*val[l-1]+dp[l][k-1][0]+dp[k+1][r][1])。

#include<bits/stdc++.h>
using namespace std;
const int N=305,INF=0x3fffffff;
int dp[N][N][2],val[N];
int main()
{
	int m,n,i,j,k,t;
	scanf("%d",&n);
	for(i=1;i<=n;i++) scanf("%d",&val[i]);
	for(i=1;i<=n;i++) dp[i][i][1]=val[i]*val[i-1],dp[i][i][0]=val[i]*val[i+1];
	for(i=1;i<=n;i++) {
		for(j=1;j+i<=n;j++)
		{
			int l=j,r=j+i; dp[l][r][0]=dp[l][r][1]=INF;
			for(k=l;k<=r;k++)
			{
				dp[l][r][0]=min(dp[l][r][0],val[k]*val[r+1]+dp[l][k-1][0]+dp[k+1][r][1]);
				dp[l][r][1]=min(dp[l][r][1],val[k]*val[l-1]+dp[l][k-1][0]+dp[k+1][r][1]);
			}
		}
	}
	printf("%d",min(dp[1][n][0],dp[1][n][1]));
}