Binomial Coefficients

[Ehump20]

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-1][k-1];
 }

This function is supposed to return the binomial coefficients for N and k using dynamic programming, but it does not return the correct result. Does anybody know what is wrong with the code?

[juanpast]

It is in Spanish but I hope it help you.

http://euitio178.ccu.uniovi.es/wiki/..._din%C3%A1mica

[Smasher/Devourer]

You have a few problems, the most obvious of which is that your nested for loops both start at zero, which means you're (a) neglecting the initial values you set up with your first for loop, and (b) passing invalid indices to your vector. To put it another way, the first execution of your inner loop is doing this:

table[0][0] = table[-1][-1] + table[-1][0];

This obviously isn't what you want. You need to start those loops at 1 instead, so they're building off your initial values. Also, is there a particular reason why you're returning the binomial coefficient (n-1 k-1) instead of (n k) as one would expect? If (n k) is what you want, then you also need to increase the dimensions of your vector. Try this:

int DynamicBinomial(int n, int k)
{
    vector< vector<int> > table(n + 1, vector<int>(k + 1));
    
    for (int j = 0; j <= n; j++) 
        table[j][0] = 1;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= k; j++)
            table[i][j] = table[i-1][j-1] + table[i-1][j];

    return table[n][k];
}

This code correctly returns the binomial coefficient (n k), although it doesn't check for invalid arguments, and also, to come to my last point, it's decidedly inefficient if you plan on calling it multiple times. Why build up a whole table of coefficients every time you call the function? It would be much better to retain your results between calls. Then when you call the function a second time, it can return a value immediately if it's already been calculated, or simply build more of the table until it gets what it needs. Or you could go with another method entirely, like using the formula (n k) = n!/(k!(n-k)!).