Dynamic programming for minimal line break costs

Question

A specific string processing language offers a primitive operation that splits a string into two parts. Since this operation involves copying the original string, it takes n time units for a string of length n, regardless of the location of the cut. Suppose now that you want to split a string into many parts. The order in which breaks are performed may affect the overall runtime. For example, if you want to cut a 20-digit string at positions 3 and 10, then at the first cut in position 3, the total cost is 20 + 17 = 37, while position 10 first has the best cost 20+ 10 = 30.

Give a dynamic programming algorithm that, given the location of m cuts in a string of length n, will find the minimum cost of dividing the string into m + 1 pieces.

This problem is taken from Chapter 6, Algorithms 6.9.

Since there is no answer to this problem, this is what I thought.

Define OPT(i,j,n) as the minimum cost of breaking the string, i for the starting index, j for the ending index String and n for the remaining amount of cut I can use.

Here is what I get:

OPT(i,j,n) = min {OPT(i,k,w) + OPT(k+1,j,nw) + ji} for i<=k<j and 0<=w<=n

Is this right or wrong? Please help, thanks!

Answer 1

I think your relapse ratio might get better. Here, what I came up with, define the cost (i, j) as the cost of cutting a line from index i to j. Then,

 cost(i,j) = min {length of substring + cost(i,k) + cost(k,j) where i < k < j} 

Answer 2

  void s_cut() { int l,p; int temp=0; //ArrayList<Integer> al = new ArrayList<Integer>(); int al[]; Scanner s=new Scanner(System.in); int table[][]; ArrayList<Integer> values[][]; int low=0,high=0; int min=0; l=s.nextInt(); p=s.nextInt(); System.out.println("The values are "+l+" "+p); table= new int[l+1][l+1]; values= new ArrayList[l+1][l+1]; al= new int[p]; for(int i=0;i<p;i++) { al[i]=s.nextInt(); } for(int i=0;i<=l;i++) for(int j=0;j<=l;j++) values[i][j]=new ArrayList<Integer>(); System.out.println(); for(int i=1;i<=l;i++) table[i][i]=0; //Arrays.s Arrays.sort(al); for(int i=0;i<p;i++) { System.out.print(al[i]+ " "); } for(int len=2;len<=l;len++) { //System.out.println("The length is "+len); for(int i=1,j=i+len-1;j<=l;i++,j++) { high= min_index(al,j-1); low= max_index(al,i); System.out.println("Indices are "+low+" "+high); if(low<=high && low!=-1 && high!=-1) { int cost=Integer.MAX_VALUE;; for(int k=low;k<=high;k++) { //if(al[k]!=j) temp=cost; cost=Math.min(cost, table[i][al[k]]+table[al[k]+1][j]); if(temp!=cost) { min=k; //values[i][j].add(al[k]); //values[i][j].addAll(values[i][al[k]]); //values[i][j].addAll(values[al[k]+1][j]); //values[i][j].addAll(values[i][al[k]]); } //else //cost=0; } table[i][j]= len+cost; values[i][j].add(al[min]); //values[i][j].addAll(values[i][al[min]]); values[i][j].addAll(values[al[min]+1][j]); values[i][j].addAll(values[i][al[min]]); } else table[i][j]=0; System.out.println(" values are "+i+" "+j+" "+table[i][j]); } } System.out.println(" The minimum cost is "+table[1][l]); //temp=values[1][l]; for(int e: values[1][l]) { System.out.print(e+"-->"); } } 

The above solution has complexity O (n ^ 3).