First of all for all substrings ,compute a boolean matrix ispalin[n][n]
which is true if a substring from i to j is a palindrome.This can be easily
done in O(n^2).
Next,let min[n][n] be the dp array,then
min[i][j]=1
,if ispalin[i][j]=1
min[i][j]=minimum(min[i][k]+min[k+1][j]) for all k>=i and k<j.
else
On Thu, Aug 25, 2011 at 6:18 PM, WgpShashank <[email protected]>wrote:
> Given a string, and split it into as few strings as possible such that
> each string is a palindrome.Example ABAABABA
> Greedy algorithm: ABAABA + B + A = 3 palindromes
> Correct answer: ABA + ABABA = 2 palindromes
>
> so one thing sure Greedy Wont Works here , so it sounds perfect DP problem
> ?
>
> Thanks
> Shashank Mani
> Computer Science
> Birla Institute of Technology Mesra
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To view this discussion on the web visit
> https://groups.google.com/d/msg/algogeeks/-/0JfJCwLmEuMJ.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
*Regards,*
*Piyush Kapoor,*
*2nd year,CSE
IT-BHU*
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
