2014
07-05

# 最优二分查找树-动态规划

Given a sorted array keys[0.. n-1] of search keys and an array freq[0.. n-1] of frequency counts, wherefreq[i] is the number of searches to keys[i]. Construct a binary search tree of all keys such that the total cost of all the searches is as small as possible.

 例 1

10                       12
\                     /
12                 10
I                     II
tree I 的花费为 34*1 + 50*2 = 134
tree II 的花费为 50*1 + 34*2 = 118

10                12                 20         10              20
\             /    \              /             \            /
12          10     20           12               20         10
\                            /                 /           \
20                        10                12             12
I               II             III             IV             V

public class OptimalSearchTree {
public static int sum(int freq[], int i, int j) {
int s = 0;
for (int k = i; k <= j; k++)
s += freq[k];
return s;
}

public static int optCost(int freq[], int i, int j) {
if (i > j)
return 0;
if (i == j) {
return freq[i];
}
//计算fsum的原因是：左右子树的高度比当前节点高度大1，因此要对所有节点重复加一次
int fsum = sum(freq, i, j);
int min = Integer.MAX_VALUE;
// 逐个考虑每个顶点为根的情况
for (int r = i; r <= j; ++r) {
int cost = optCost(freq, i, r - 1) + optCost(freq, r + 1, j);
if (cost < min)
min = cost;
}
return min + fsum;
}

public static void main(String[] args) {
int freq[] = {34, 8, 50};
System.out.println("Cost of Optimal BST is "+ optCost(freq, 0 , freq.length-1));
}
}

	public static int optCostDP(int freq[]) {
int n = freq.length;
int dp[][] = new int[n][n];
for (int i = 0; i < n; i++)
dp[i][i] = freq[i];

// l表示树的节点个数
for (int l = 2; l <= n; l++) {
for (int i = 0; i <= n - l; i++) {
// 从i到j，长度为l
int j = i + l - 1;
dp[i][j] = Integer.MAX_VALUE;
for (int r = i; r <= j; r++) {
int c = ((r > i) ? dp[i][r - 1] : 0)
+ ((r < j) ? dp[r + 1][j] : 0) + sum(freq, i, j);
if (c < dp[i][j])
dp[i][j] = c;
}
}
}
return dp[0][n-1];
}

1) 上面算法的时间复杂度为 O(n^4). 可以很容易的优化到 O(n^3) ，主要是对于sum函数，可以预处理所有的和。

2）上面的算法只求出了最小花费，并没有给出树的机构，稍作修改即可构建树。在最内层的循环记录下r（根节点）即可。

1. int half(int *array,int len,int key)
{
int l=0,r=len;
while(l<r)
{
int m=(l+r)>>1;
if(key>array )l=m+1;
else if(key<array )r=m;
else return m;
}
return -1;
}
这种就能避免一些Bug
l,m,r
左边是l,m;右边就是m+1,r;