//本程序取自王曉東編著“算法分析與設計”第 100 頁，例
//最優二叉搜索樹問題動態規劃改進解法

 public class Fac3_10_1{             
   public static void obst(float a[],float b[],float [][]m,int [][]s,float[][] w)
     {
       int n=a.length-1;
       for(int i=0;i<=n;i++){
         w[i+1][i]=a[i];
         m[i+1][i]=0;
         s[i+1][i]=0;
        }
       for(int r=0;r<n;r++)
         for(int i=1;i<=n-r;i++){
           int j=i+r;
           int i1=s[i][j-1]>i? s[i][j-1]:i;
           int j1=s[i+1][j]>i? s[i+1][j]:j;
           w[i][j]=w[i][j-1]+a[j]+b[j];
           m[i][j]=m[i][i1-1]+m[i1+1][j];
           s[i][j]=i1;
           for(int k=i1+1;k<=j1;k++){
           float t=m[i][k-1]+m[k+1][j];
           if(t<=m[i][j]){
                m[i][j]=t;
                s[i][j]=k;
              }
           }
        m[i][j]+=w[i][j];
      }
     
   }
      public static void main(String args[])
  {
   float a1[]={0.06f,0.03f,0.05f,0.04f,0.06f,0.1f};
    float b1[]={0.0f,0.2f,0.2f,0.06f,0.1f,0.1f};
    int n1=a1.length;  
    int n2=b1.length;
    float m1[][]=new float[n1+1][n2+1] ;    
    int s1[][]=new int[n1+1][n2+1];
    float [][]w1=new float[n1+1][n2+1];
    obst(a1,b1,m1,s1,w1);
    System.out.println("輸出二叉最優搜索樹根結點元素  ");
    for(int i=1;i<n1;i++){
     for(int j=1;j<n2;j++)
    System.out.print(s1[i][j]+"  ");
    System.out.println();
   }
  }
}