import java.util.Arrays;public class Test {		public static void main(String args[]){		optimalBST(p, q, n);	}			// 5个互异关键字组成的序列，且关键字有序。	public static int n = 5;	// 每个关键字对应的被搜索到的概率	public static float[] p = {0f, 0f, 0.15f, 0.10f, 0.05f, 0.10f, 0.20f};		// 搜索不到的概率	public static float[] q = {0f, 0.05f, 0.10f, 0.05f, 0.05f, 0.05f, 0.10f};	// 由底向上处理	public static void optimalBST(float[] p, float[] q, int n){		float t = Float.MAX_VALUE;		float[][] root = new float[n + 1][n + 1];				float[][] e = new float[n + 2][n + 1];		float[][] w = new float[n + 2][n + 1];				for (int i = 1; i < n + 2; i++) {			e[i][i - 1] = q[i];			w[i][i - 1] = q[i];		}				for (int l = 1; l <= n; l++) {			for (int i = 1; i <= n - l + 1; i++) {				int j = i + l - 1;				e[i][j] = Float.MAX_VALUE;				w[i][j] = w[i][j - 1] + p[j + 1] + q[j + 1]; 				for (int k = i; k <= j; k++) {					t = e[i][k - 1] + e[k + 1][j] + w[i][j];					if(t < e[i][j]){						e[i][j] = t;						root[i][j] = k;					}				}			}		}						for (int i = 0; i < e.length; i++) {			System.out.println(Arrays.toString(e[i]));		}				System.out.println("####################");				for (int i = 0; i < w.length; i++) {			System.out.println(Arrays.toString(w[i]));		}		System.out.println("####################");				for (int i = 0; i < root.length; i++) {			System.out.println(Arrays.toString(root[i]));		}	}}