package org.xiu68.ch06.ex6;

 public class Ex6_9 {

     public static void main(String[] args) {

         // TODO Auto-generated method stub

         //分割的最小代价为：30

         //分割顺序为: 10 3

         int[] arr=new int[]{1,3,10,20};          //设开始点为1和20，中间三个点为拆分点

         int[][] splitPoint=new int[arr.length+1][arr.length+1];

         minSplitCost(arr,splitPoint);

         System.out.print("分割顺序为: ");

         printSplitPoint(arr,splitPoint,1,arr.length);

         System.out.println();

         //分割的最小代价为：48

         //分割顺序为: 10 8 2

         int[] arr2=new int[]{1,2,8,10,30};

         int[][] splitPoint2=new int[arr2.length+1][arr2.length+1];

         minSplitCost(arr2,splitPoint2);

         System.out.print("分割顺序为: ");

         printSplitPoint(arr2,splitPoint2,1,arr2.length);

     }

     public static void minSplitCost(int[] arr,int[][] splitPoint){

         int[][] cost=new int[arr.length+1][arr.length+1];

         int length=arr.length;

         for(int s=2;s<=length;s++){                //分割点的个数

             for(int i=1;i<=length-s+1;i++){        //第一个分割点

                 int j=i+s-1;                    //最后一个分割点

                 if(j-i>=2)                        //两个分割点之间要有大于一个的分割点才能继续分割

                     cost[i][j]=Integer.MAX_VALUE;

                 for(int k=i+1;k<=j-1;k++){        //寻找分割子串最小代价对应的分割位置

                     int temp=cost[i][k]+cost[k][j]+arr[j-1]-arr[i-1]+1;

                     if(temp<cost[i][j]){

                         cost[i][j]=temp;

                         splitPoint[i][j]=k;

                     }

                 }//

             }//

         }//

         System.out.println("分割的最小代价为："+cost[1][length]);

     }

     public static void printSplitPoint(int[]arr,int[][] splitPoint,int i,int j){

         if(j-i>=2){

             System.out.print(arr[splitPoint[i][j]-1]+" ");

             printSplitPoint(arr,splitPoint,i,splitPoint[i][j]);

             printSplitPoint(arr,splitPoint,splitPoint[i][j],j);

         }

     }

 }