title: Dynamic Programming Breaking a String
body: <p>The goal is to calculate the cost of breaking the string at the break points given by the user. So lets assume the following:
  The length of String =  10 so lengthArray = [1,2,3,4,5,6,7,8,9,10]
  and BreakPointArray = [5, 3, 2, 6, 1]. Now we do not have to change the order of the breaks given by the user.</p>
  
  <p>I am able to figure out the tree structure for this problem </p>
  
  <p><img src="https://i.stack.imgur.com/WFZCs.png" alt="enter image description here"></p>
  
  <p>So the total cost of breaking the String at the breakPoints given = 10+5+5+3+2 = 25
  However I am not able to come up with the implementation part. Below is my approach :</p>
  
  <p>I start from BreakPoint = 5 and divide the lengthArray into </p>
  
  <p>leftLength = [1,2,3,4,5]</p>
  
  <p>and</p>
  
  <p>rightLength = [6,7,8,9,10]</p>
  
  <p>at BreakPoint = 3 , I check that it should come under leftLength Array so again I divide leftLength into 2 parts</p>
  
  <p>leftLength1 = [1, 2,3] </p>
  
  <p>and </p>
  
  <p>rightLength1 = [4,5] </p>
  
  <p>at BreakPoint = 2, come under leftLength1 so again divide into 2 parts</p>
  
  <p>leftLength2 = [1,2] and </p>
  
  <p>rightLength2 = [3]</p>
  
  <p>Now I get stuck when BreakPoint = 6, since it comes under rightLength above. Can someone please help how can i keep track of all the partitions I have done . How can i go back to first rightLength array to compute cost for breakPoint 6. I am trying to implement this Java. </p>