Binomial Coefficient is represented by nCk which means number of ways of choosing k objects from n objects.It is the coefficient of x^k term in the polynomial expansion of (1+x)^n.It also represents an entry in Pascals Triangle.
Properties-
1. nCk=(n!)/[(k!)*(n-k)!]
2. nCn=1
3. nC0=1
4. nCk=(n-1)C(k)+(n-1)C(k-1)
5. nCk=(n)C(n-k)
The task is to find the value of nCk given the values of n and k.
Recursive solution-
[cpp]
int binomialCoeff(int n, int k)
{
// Base Cases
if (k==0 || k==n)
return 1;
// Recurrence
return binomialCoeff(n-1, k-1) + binomialCoeff(n-1, k);
}
[/cpp]
For large values of n,there will be many common subproblems.For example-
To calculate 5C2,function will be called for 4C2 and 4C1.
To calculate 4C1,function will be again called for 3C0 and 3C1.
To calculate 4C2,function will be called for 3C1 and 3C2.
So,3C1 is being calculated twice.
This problem has overlapping sub-problems property.Re-computation of same sub-problems can be avoided by constructing a temporary array C[][] and storing the results like we do in other dynamic programming problems.
DP based solution-
[cpp]
//C[][] is the temp array
for(i=0;i<=n;i++)
{
for(j=0;j<=i;j++)
{
//base condition
if((i==0)||(j==0)) C[i][j]=1;
else C[i][j]=C[i-1][j-1]+C[i-1][j];
}
}
//C[n][k] gives the result
[/cpp]
Time Complexity of this code is O(n*k).
Note-
n,k are non negative integers.
nCk is valid only for n>0 and 0<=k<=n.
