/* * Copyright (C) 2003-2008 Wang Pengcheng <wpc0000@gmail.com> * 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 2008package 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;	}}