Use complete search, add memoization and you have a top-down dynamic programming solution ready.
- lets say we have division positions in an array cuts[] - start and end will identify the position of current cut (taken from cuts[] array) - initialize memo[][] array to INT_MAX, this is the place where you will be holding solutions to the subproblems int cut(int start, int end) { if (start + 1 == end) return 0; if (memo[start][end] != INT_MAX) return memo[start][end]; for (int i = start + 1; i < end; i++) { memo[start][i] = cut(start, i); memo[i][end] = cut(i, end); memo[start][end] = min(memo[start][end], memo[start][i] + memo[i][end] + cuts[end] - cuts[start]; } return memo[start][end]; } So if we have for example a string with length 100 and cuts can be made at 25, 50 and 75 then your solution should do this: - cuts[] will have [0, 25, 50, 75] (0 is added for adding simplicity to coding) - we start our complete search with solve(0, 5) where 0 and 5 are indexes in cuts[] array (yes 5 is out of bound but we need it as an upper bound) - in our solve() methods we first check if start + 1 == end which identifies that we have reached a situation with a segment without any cuts in the middle - then we check if we have the solution for this subproblem already cached in our memo[][] (as we might have encountered it earlier) - finally if those first 2 checks didn't succeed we go through all the positions in cuts[] array which lie between start and end and try cutting: * solve(0, 1) + solve(1, 5) * solve(0, 2) + solve(2, 5) * solve(0, 3) + solve(3, 5) * solve(0, 4) + solve(4, 5) - we also save every single result of the subproblem we encounter in memo - finally the cost of cutting for every problem/subproblem is looking like this: cost of cutting (start, i) plus cost of cutting (i, end) + the cost of cutting the length of the current string Hope it helps, Konstantin On Jul 8, 5:23 pm, Rakib Ansary Saikot <ansaryfantas...@gmail.com> wrote: > 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. > > 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.