It can be solved with trie On Sun, Jul 18, 2010 at 10:28 AM, Ashish Goel <[email protected]> wrote:
> dp[i][0]=1 implies that there is 1 combination which will ensure that the > number of A's and B's is same in the string. > eg AAA is not a valid string > > dp[0][0]=1 doesnot satisfy property 1 either > > with this algo and tring length 4(possible strings AABB, ABAB) > > > a[i][j] will look like > > 1 1 1 > 0 1 0 > 0 1 1 > > > also, donot understand the logic why n/2 is chosen? > > > > Best Regards > Ashish Goel > "Think positive and find fuel in failure" > +919985813081 > +919966006652 > > > > On Tue, Jul 13, 2010 at 3:39 AM, Amir hossein Shahriari < > [email protected]> wrote: > >> dp[i][j] is the number of strings that have i As and j Bs >> >> >> dp[0][0]=1; // s="" >> for (i=1;i<=n/2;i++) >> >> dp[i][0]=1; // s="AAA..." >> >> for (i=1;i<=n/2;i++) >> >> dp[0][i]=0; // the 2nd constraint >> >> for (i=1;i<=n/2;i++) >> >> for (j=1;j<=n/2;j++) >> >> if (j>i) >> >> dp[i][j]=0; // the 2nd constraint >> >> else >> >> dp[i][j]=dp[i-1][j]+dp[i][j-1]; >> >> >> dp[n/2][n/2] would be the result >> >> -- >> 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]<algogeeks%[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]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Rahul singhal RnD Engineer Tejas Networks Mobile- 09916969422 -- 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.
