最优二叉搜索树，四边形优化貌似也是从这里衍生出来的定理。这题和矩阵链乘很像。
题意：给你一个排好序的关键字出现概率的集合。要求一个满足条件的最优二叉搜索树，至于最优二叉搜索树的定义在题目描述里面有。
w[i][j]表示集合中第i个到第j个元素的累积概率和。e[i][j]表示集合中使用第i个到第j个元素的最优二叉搜索树的花费，那么e[i][i] = 0;
那么状态转移方程就为:e[i][j] = e[i][k-1]+e[k+1][j]+w[i][j]-f[k](i<=k<=j),即枚举i到j之间的所有元素为根节点，最优结果e[1][n]即为所求。
#include <stdio.h>
#include <string.h>
#define N 255
#define INF 1 << 28
int e[N][N], w[N][N], f[N];
int main()
{
int n;
while(~scanf("%d", &n))
{
memset(w, 0, sizeof(w));
memset(e, 0, sizeof(e));
for(int i = 1; i <= n; i++)
scanf("%d", &f[i]);
for(int i = 1; i <= n; i++)
for(int j = i; j <= n; j++)
w[i][j] = w[i][j - 1] + f[j];
for(int i = 2; i <= n; i++)
for(int j = i - 1; j; j--)
{
e[j][i] = INF;
for(int k = j; k <= i; k++)
{
if(e[j][k - 1] + e[k + 1][i] + w[j][i] - f[k] < e[j][i])
{
e[j][i] = e[j][k - 1] + e[k + 1][i] + w[j][i] - f[k];
}
}
}
printf("%d\n", e[1][n]);
}
return 0;
}