O(N^3) DP
-------------------------------------------------------------------------------------------------------------
char str[MAX];
int dp1[MAX][MAX],dp2[MAX][MAX];
int isPalin(int low,int high)
{
if(low>=high) return 1;
if(dp1[low][high]!=-1) return dp1[low][high];
return dp1[low][high]=(str[low]==str[high])?isPalin(low+1,high-1):0;
}
int minCuts(int low,int high)
{
if(isPalin(low,high)) return 0;
if(dp2[low][high]!=-1) return dp2[low][high];
int ans=1e9;
for(int i=low;i<high;i++)
ans=min(ans,1+minCuts(low,i)+minCuts(i+1,high));
return dp2[low][high]=ans;
}
-------------------------------------------------------------------------------------------------------------
On Fri, May 6, 2011 at 4:23 PM, sourabh jakhar <[email protected]>wrote:
> You are given a large string. You need to cut the string into chunks such
> that each substring that you get is a palindrome. Remember that each 1
> length string is always a palindrome. You need to find the minimum number of
> cuts that you need to make such that each substring is a palindrome.
> <http://www.careercup.com/question?id=8972527>
>
> --
> SOURABH JAKHAR,(CSE)(3 year)
> ROOM NO 167 ,
> TILAK,HOSTEL
> 'MNNIT ALLAHABAD
>
> The Law of Win says, "Let's not do it your way or my way; let's do it the
> best way."
>
> --
> 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.
>
--
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.
