dp1[i][j] will hold 1/0 depending upon whether string str[i...j] is a
palindrome or not.
Now let dp2[i][j] be the minimum number of cuts required to split it into
palindromes.
if str[i...j] is a palindrome then '0' cuts are required.
To get the number of cuts required for str[i...j] we try all possible
positions between i & j and take minimum of all.
On Fri, May 6, 2011 at 8:23 PM, sourabh jakhar <sourabhjak...@gmail.com>wrote:
> can you explain the logic
>
>
> On Fri, May 6, 2011 at 8:02 PM, abhijith reddy
> <abhijith200...@gmail.com>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
>> <sourabhjak...@gmail.com>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 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.
>>>
>>
>> --
>> 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.
>>
>
>
>
> --
> 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 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.
>
--
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.
