1) Optimal Substructure
The value of C(n, k) can recursively calculated using following standard formula for Binomial Cofficients.
Space and time efficient Binomial Coefficient
UVa 530: Binomial Showdown
Read full article from Dynamic Programming | Set 9 (Binomial Coefficient) | GeeksforGeeks
The value of C(n, k) can recursively calculated using following standard formula for Binomial Cofficients.
C(n, k) = C(n-1, k-1) + C(n-1, k)
C(n, 0) = C(n, n) = 1
int
binomialCoeff(
int
n,
int
k)
{
int
C[n+1][k+1];
int
i, j;
// Caculate 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 previosly stored values
else
C[i][j] = C[i-1][j-1] + C[i-1][j];
}
}
return
C[n][k];
}
Following is a space optimized version of the above code. The following code only uses O(k).
// A space optimized Dynamic Programming Solution int binomialCoeff( int n, int k) { int * C = ( int *) calloc (k+1, sizeof ( int )); int i, j, res; C[0] = 1; for (i = 1; i <= n; i++) { for (j = min(i, k); j > 0; j--) C[j] = C[j] + C[j-1]; } res = C[k]; // Store the result before freeing memory free (C); // free dynamically allocated memory to avoid memory leak return res; } |
The value of C(n, k) can be calculated in O(k) time and O(1) extra space.
C(n, k) = n! / (n-k)! * k!
= [n * (n-1) *....* 1] / [ ( (n-k) * (n-k-1) * .... * 1) *
( k * (k-1) * .... * 1 ) ]
After simplifying, we get
C(n, k) = [n * (n-1) * .... * (n-k+1)] / [k * (k-1) * .... * 1]
Also, C(n, k) = C(n, n-k) // we can change r to n-r if r > n-r
int
binomialCoeff(
int
n,
int
k)
{
int
res = 1;
// Since C(n, k) = C(n, n-k)
if
( k > n - k )
k = n - k;
// Calculate value of [n * (n-1) *---* (n-k+1)] / [k * (k-1) *----* 1]
for
(
int
i = 0; i < k; ++i)
{
res *= (n - i);
res /= (i + 1);
}
return
res;
}
public
static
long
Factorial(
int
n) {
long
res =
1
;
// n! = 1 * 2 * 3 * ... * (n - 1) * n
for
(
int
i =
1
; i <= n; i++) {
res *= i;
}
return
res;
}
// computes n choose k
public
static
long
Choose(
int
n,
int
k) {
// n choose k = n! / (k! * (n - k)!)
return
Factorial(n) / (Factorial(k) * Factorial(n - k));
}
public
static
long
Choose(
int
n,
int
k) {
long
res =
1
;
// n choose k = the product of (n - k + i) / i for i = 1..k
for
(
int
i =
1
; i <= k; i++) {
res = res * (n - k + i) / i;
}
return
res;
}
It can easily be derived:
public
static
long
Choose(
int
n,
int
k) {
// n choose k is equal to n choose (n - k),
// so we pick the one that is easier to compute,
// which is the smaller one
k = Math.min(k, n - k);
long
res =
1
;
// n choose k = the product of (n - k + i) / i for i = 1..k
for
(
int
i =
1
; i <= k; i++) {
res = res * (n - k + i) / i;
}
return
res;
}