can u please explain me in descriptive manner On Sat, May 7, 2011 at 2:31 PM, Amir hossein Shahriari < amir.hossein.shahri...@gmail.com> wrote:
> @venkatesan : im not sure about that! this problem is different > > but we can do it in O(n^2) > the DP1 can be built done in O(n^2) as in abhijith's solution > also the DP2 can be built in O(n^2) too. instead of counting the min # of > palindrome strings that can make the range of [low,high] > count how many palindromes can make the range [0,x] > this makes the dp2 array linear and the overall running time quadratic > > int minCuts(int x) > { > if(isPalin(0,x)) return 0; > if(dp2[x]!=-1) return dp2[x]; > int ans=1e9; > for(int i=1;i<high;i++) > if (isPalin(i,x)) > ans=min(ans,1+minCuts(i-1)); > return dp2[x]=ans; > } > > > On Sat, May 7, 2011 at 12:41 PM, venkatesan B < > venkat_b_engin...@yahoo.co.in> wrote: > >> problem like to find largest palindrome in the string >> so, in O(n) time complexity to find largest palindrome in the string >> >> >> ------------------------------ >> *From:* hary rathor <harry.rat...@gmail.com> >> *To:* algogeeks@googlegroups.com >> *Sent:* Saturday, 7 May 2011 10:33 AM >> *Subject:* Re: [algogeeks] >> >> @venkatesan >> >> now you give the algorithm ... of O(n) >> -- >> 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. >> > > -- > 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.