Heres a problem that I've been trying to solve using Dynamic Programming but I've got no where with it. Any hints would be appreciated.
A program's library offers a simple function to split a string into two parts. As this operation requires copying the entire string, it takes time n, where n is the length of the original string, regardless of the position of division. Suppose now that you have to split a string into several parts, using only the offered function. The series will be the individual divisions affects the total time required. For example, to split a string of 20 characters in positions 3 and 10 ,where the first splitting done into place 3 the total time required is 20+17=37 while if the first splitting will be done into place 10 the total time is 20+10=30. Develop and implement a dynamic programming algorithm which, if given the m positions where we want to divide a string of length n, finds the minimum cost of this division into m+1 sections. Calculate the temporal and spatial complexity of your algorithm. *examples* * *A string length 100 divided in positions 25, 50, 75: the minimum cost is 200. * *A string length 10 divided in positions 4, 5, 7, 8: the minimum cost is 22. Thank you. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
