simpleoptimalbst.java

来自「<算法导论>第二版大部分算法实现. 1. 各类排序和顺序统计学相关」· Java 代码 · 共 45 行

/*
 * Copyright (C) 2003-2008 Wang Pengcheng <[e-mail]>
 * Permission is granted to copy, distribute and/or modify this
 * document under the terms of the GNU Free Documentation License,
 * Version 2.0 or any later version published by the Free Software Foundation;
 * with no Invariant Sections.
 * You may obtain a copy of the License at
 *   http://www.gnu.org/licenses/lgpl.txt
 */
//19 Feb 2008
package cn.edu.whu.iss.algorithm.unit15.optimalbst;

public class SimpleOptimalBST extends AbstractOptimalBST {

	private double[][] e;
	private double[][] w;
	
	public double optimalBST() {
		e = new double[n+2][n+1];
		w = new double[n+2][n+1];
		root = new int[n+1][n+1];
		for(int i=1;i<=n+1;i++){
			e[i][i-1] = q[i-1];
			w[i][i-1] = q[i-1];
		}
		for(int l=1;l<=n;l++){
			for(int i=1;i<=n-l+1;i++){
				int j = i+l-1;
				e[i][j] = Double.MAX_VALUE;
				w[i][j] = w[i][j-1]+p[j-1]+q[j];
				for(int r = i;r<=j;r++){
					double t = e[i][r-1]+e[r+1][j]+w[i][j];
					if(t<e[i][j]){
						e[i][j] = t;
						root[i][j] = r;
					}
				}
			}
		}
		ans = e[1][n];
		return ans;
	}

}