GATE CSE
First time here? Checkout the FAQ!
x
0 votes
54 views
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.
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. You may assume that all m locations are in the interior of the string so each split is non-trivial.
asked in Algorithms by Veteran (75.6k points)   | 54 views

Please log in or register to answer this question.

Top Users Feb 2017
  1. Arjun

    5166 Points

  2. Bikram

    4204 Points

  3. Habibkhan

    3748 Points

  4. Aboveallplayer

    2986 Points

  5. sriv_shubham

    2298 Points

  6. Debashish Deka

    2234 Points

  7. Smriti012

    2142 Points

  8. Arnabi

    1998 Points

  9. mcjoshi

    1626 Points

  10. sh!va

    1552 Points

Monthly Topper: Rs. 500 gift card

20,815 questions
25,974 answers
59,606 comments
22,025 users