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 <[email protected]> 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 [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.
