can you explain the logic
On Fri, May 6, 2011 at 8:02 PM, abhijith reddy <[email protected]>wrote:
> 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.
>
--
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.
