最優二叉搜索樹，四邊形優化貌似也是從這里衍生出來的定理。這題和矩陣鏈乘很像。
題意：給你一個排好序的關鍵字出現概率的集合。要求一個滿足條件的最優二叉搜索樹，至于最優二叉搜索樹的定義在題目描述里面有。
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;
}