but it is O(N^2)...will give TLE
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.
>
>
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
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.
