hey 1Cn is not 1.. On Tue, Jun 21, 2011 at 2:33 PM, ross <jagadish1...@gmail.com> wrote:
> A small correction, j = 0 to i. > > On Jun 21, 2:01 pm, ross <jagadish1...@gmail.com> wrote: > > Hi, > > Ya DP with memoization is best.. > > > > nCr= n-1Cr-1 + n-1 C r > > > > DP]i,j] = DP[i-1,j-1] + DP[i-1,j]; > > > > (LINEAR SPACE COMPLEXITY is possible because at each time we require > > only 2 rows of the matrix) > > > > Base Cases, > > nCn = 1. DP[i,i]=1. > > 1Cn = 1 DP[1,j] =1. > > nC1 = n . > > nC0 = 1 > > > > for ( i = 0 - N ) > > for ( j= i - N ) > > { > > if(i == j) dp[i.j] =1. > > else if (j==1) dp[i j ] = i; > > else if (j == 0) dp [ i j] = 1; > > else > > DP]i,j] = DP[i-1,j-1] + DP[i-1,j]; > > > > } > > > > On Jun 21, 1:34 pm, kartik sachan <kartik.sac...@gmail.com> wrote: > > > > > > > > > > > > > > > > > but for big numbers this method is very expensive................and > hope > > > give TLE in 1 sec question where n=1000 > > -- > 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.