Dynamic Programming | Set 9 (Binomial Coefficient) | GeeksforGeeks

1) Optimal Substructure
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; }

Space and time efficient Binomial Coefficient

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;

}

UVa 530: Binomial Showdown

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;

}

Read full article from Dynamic Programming | Set 9 (Binomial Coefficient) | GeeksforGeeks