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]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
