Question

A certain string-processing language offers a primitive operation which splits a string into two pieces. Since this operation involves copying the original string, it takes n units of time for a string of length n, regardless of the location of the cut. Suppose, now, that you want to break a string into many pieces. The order in which the breaks are made can affect the total running time. For example, if you want to cut a 20-character string at positions 3 and 10, then making the first cut at position 3 incurs a total cost of 20 + 17 37, while doing position 10 first has a better cost of 20 + 10 30.
Required:
Give a dynamic programming algorithm that, given the locations of m cuts in a string of length n, finds the minimum cost of breaking the string into m + 1 pieces.

Answer 1

Answer:

Explanation:

First we define define cost(i,j) to be the cost of cutting the string from index i to j. Then,

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

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+"-->");

   }