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

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

}