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.
