Binomial Coefficients

#1

// C++ program for space optimized Dynamic Programming
// Solution of Binomial Coefficient
#include<bits/stdc++.h>
using namespace std;

int binomialCoeff(int n, int k)
{
int C[k+1];
memset(C, 0, sizeof©);

C[0] = 1;  // nC0 is 1

for (int i = 1; i <= n; i++)
{
    // Compute next row of pascal triangle using
    // the previous row
    for (int j = min(i, k); j > 0; j--)
        C[j] = C[j] + C[j-1];
}
return C[k];

}

can someone tell me why int j = min(i, k) in inner for loop

#2

Yeah ! because nCk can be expressed as a sum of nCr where r is always less then k so we have to avoid the case with r>k
this is not much time efficient you can prefer Lucasapproach for calculating nCr (which is the best approach)
:wink:

1 Like