Categories: MSDN / DotNet / Java / Scripts / Linux / PHP Ask - La ask - La Answer

Binomial Coefficients

int dynamicBinomial(int N, int k)
{
vector< vector<int> >table(N,vector<int>(k));

for (int j = 0; j < N; j++)
table[j][0] = 1;

for (int i = 0; i < N; i++)
{
for (int j = 0; j < k; j++)
{
table[i][j] = table[i-1][j-1] + table[i-1][j];
}
}
return table[N][k];
}

This code is supposed to return the binomial coefficient of N and k but is not working properly. Anybody know what is wrong with the code?
[541 byte] By [EHump20] at [2007-11-11 10:30:16]
# 1 Re: Binomial Coefficients
Hi,
I haven't tried, but I guess your problem is the return:
Should be:

return table[N-1][k-1];

You have 0-based indices, so binomial-coefficient(3,8) is aactually saved in your table at position 2,7.

Cheers,

D
drkybelk at 2007-11-11 20:58:39 >