package com.dynamic;

import java.text.DecimalFormat;

public class OptimalSearchTree {
  private double [] p;//关键字概率
  private double [] q;//不在树中的关键字概率
  private int [] k;//关键字
  //private int [][]d;//不在树中的关键字
  private double[][]e;
  private double[][]w;
  private int[][]root;
  public OptimalSearchTree(int[]k,double [] p,double []q)throws Exception{
    if(k.length+1!=p.length){
      throw new Exception("数据错误");
    }
    if(k.length+1!=q.length){
      throw new Exception("数据错误");
    }
    double sum=0;
    for(int i=0;i<p.length;i++){
      sum+=p[i];
    }
    for(int j=0;j<q.length;j++){
      sum+=q[j];
    }
    DecimalFormat format=new DecimalFormat("0.00");
    if(Double.parseDouble(format.format(sum))!=1.0){
      throw new Exception("数据错误");
    }
    this.q=q;
    this.p=p;
    this.k=k;
    e=new double[p.length+1][p.length+1];
    w=new double[p.length+1][p.length+1];
    root=new int[p.length][p.length];
    for(int i=0;i<w.length;i++){
      for(int j=0;j<w[i].length;j++){
        w[i][j]=-1;
      }
    }
    for(int i=0;i<e.length;i++){
      for(int j=0;j<e[i].length;j++){
        e[i][j]=Integer.MAX_VALUE;
      }
    }
    
  }
  private double innerOptimal(int i,int j){
    if(e[i][j]!=Integer.MAX_VALUE){
      return e[i][j];
    }
    if(j==i-1){
      e[i][j]=q[i-1];
    }else{
      double tmp=Integer.MAX_VALUE;
      for(int r=i;r<=j;r++){
        tmp=innerOptimal(i,r-1)+innerOptimal(r+1,j)+computeW(i,j);
        if(tmp<e[i][j]){
          e[i][j]=tmp;
          root[i][j]=r;
        }
      }
    }
    return e[i][j];
  }
  private double computeW(int i,int j){
    if(w[i][j]>=0){
      return w[i][j];
    }else{
      double tmp=0;
      for(int l=i;l<=j;l++){
        tmp+=p[l];
      }
      for(int l=i-1;l<=j;l++){
        tmp+=q[l];
      }
      w[i][j]=tmp;
      return tmp;
    }
  }
  public void printTree(){
    innerPrintTree(1,k.length,-1);
  }
  private void innerPrintTree(int i,int j,int parent){
    if(i>j){
      return;
    }
    if(i==1&&j==k.length){
      System.out.println("    "+root[i][j]);
    }else{
      System.out.println(root[i][j]+","+parent);  
    }
    innerPrintTree(i,root[i][j]-1,root[i][j]);
    innerPrintTree(root[i][j]+1,j,root[i][j]);
  }
  public double optimal(){
    double ret=innerOptimal(1,k.length);
    return ret;
  }
  public static void main(String[] args) throws Exception{
    int [] k=new int[]{1,2,3,4,5};
    double [] p=new double[]{0,0.15,0.10,0.05,0.10,0.20};
    double [] q=new double[]{0.05,0.10,0.05,0.05,0.05,0.10};
    OptimalSearchTree ost=new OptimalSearchTree(k,p,q);
    System.out.println(ost.optimal());
    ost.printTree();
  }

}