Binomial Coefficient

Applications:

1. Pascal’s Triangle
2. Cases where the path/answer is f(i-1,j-1) + f(i-1,j) (since nCk = n-1Ck-1 + n-1Ck)

Complexity : O(n*k)

int binomialCoeff(int n, int k)
{
int C[n + 1][k + 1];
int i, j;
// Calculate value of Binomial Coefficient
// in bottom up manner
for (i = 0; i <= n; i++) {
for (j = 0; j <= min(i, k); j++) {
// Base Cases
if (j == 0 || j == i)
C[i][j] = 1;
// Calculate value using previously
// stored values
else
C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
}
}
return C[n][k];
}

Sample problem

http://codeforces.com/contest/559/problem/C