设字符串的长度为n,整型数组arr[0. . .n-1]的第一个数和最后一个数为开始点与结束点的位置,中间的数为拆分点的位置,设cost[i,j]为第i个分割点到第j个分割点的最小代价,两个分割点之间要有大于等于一个分割点才能把字符串继续拆分,因此j-i>=2; 得到递推式
1 package org.xiu68.ch06.ex6; 2 3 public class Ex6_9 { 4 5 public static void main(String[] args) { 6 // TODO Auto-generated method stub 7 //分割的最小代价为:30 8 //分割顺序为: 10 3 9 int[] arr=new int[]{1,3,10,20}; //设开始点为1和20,中间三个点为拆分点10 int[][] splitPoint=new int[arr.length+1][arr.length+1];11 minSplitCost(arr,splitPoint);12 System.out.print("分割顺序为: ");13 printSplitPoint(arr,splitPoint,1,arr.length);14 System.out.println();15 16 17 //分割的最小代价为:4818 //分割顺序为: 10 8 2 19 int[] arr2=new int[]{1,2,8,10,30};20 int[][] splitPoint2=new int[arr2.length+1][arr2.length+1];21 minSplitCost(arr2,splitPoint2);22 System.out.print("分割顺序为: ");23 printSplitPoint(arr2,splitPoint2,1,arr2.length);24 }25 26 27 public static void minSplitCost(int[] arr,int[][] splitPoint){28 int[][] cost=new int[arr.length+1][arr.length+1];29 int length=arr.length;30 for(int s=2;s<=length;s++){ //分割点的个数31 for(int i=1;i<=length-s+1;i++){ //第一个分割点32 int j=i+s-1; //最后一个分割点33 if(j-i>=2) //两个分割点之间要有大于一个的分割点才能继续分割34 cost[i][j]=Integer.MAX_VALUE;35 for(int k=i+1;k<=j-1;k++){ //寻找分割子串最小代价对应的分割位置36 int temp=cost[i][k]+cost[k][j]+arr[j-1]-arr[i-1]+1;37 if(temp=2){49 System.out.print(arr[splitPoint[i][j]-1]+" ");50 printSplitPoint(arr,splitPoint,i,splitPoint[i][j]);51 printSplitPoint(arr,splitPoint,splitPoint[i][j],j);52 }53 }54 }