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; }

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