Dynamic programming

In the last lesson, you saw how to implement an algorithm for calculating the Fibonacci numbers efficiently. In that algorithm, we only needed memory for two numbers, and we updated those two local variables when calculating the $n$^th Fibonacci number. We will now look at calculating the binomial coefficients ${n \choose k}$.

You will remember from secondary school that the binomial coefficients arise naturally in mathematics where, for example,

$(x + 1)^n = {n \choose 0}x^n + {n \choose 1}x^{n - 1} + {n \choose 2}x^{n - 2} + {n \choose 3}x^{n - 3} + \cdots + {n \choose n - 3}x^3 + {n \choose n - 2}x^2 + {n \choose n - 1}x + {n \choose n}$.

where some are reasonably easy to determine:

$(x + 1)^n = x^n + n x^{n - 1} + {n \choose 2}x^{n - 2} + {n \choose 3}x^{n - 3} + \cdots + {n \choose n - 3}x^3 + {n \choose n - 2}x^2 + nx + 1$.

You will recall that ${n \choose k} = \frac{n!}{k!(n - k)!}$ for $k$ going from $0$ to $n$ with the value being zero otherwise. This can be calculated recursively using the formula ${n \choose k} = {n - 1 \choose k} + {n - 1 \choose k - 1}$ if $k > 0$ or $k < n$.

Suppose we calculated the Binomial coefficients using the following recursively defined function:

#include <iostream>
unsigned long binomial( unsigned long n, unsigned long k );
int main();

unsigned long binomial( unsigned long n, unsigned long k ) {
	if ( k > n ) {
		return 0;
	} else if ( (k == 0) || (k == n) ) {
		return 1;
	} else {
		return binomial( n - 1, k ) + binomial( n - 1, k - 1 );
	}
}

int main() {
	unsigned long n{40};

	for ( unsigned long k{0}; k <= n; ++k ) {
		std::cout << "binomial(" << n << "," << k << ") = "
		          << binomial( n, k ) << std::endl;
	}

	return 0;
}

Note: If you are running this in cpp.sh, please use n{29}, otherwise the algorithm times out.

Now, give that C++ is doing billions of calculations, should it not be easier to just generate Pascal's triangle up to $n = 40$?

Consider Pascal's triangle up to $n = 14$:

Suppose we are calculating ${14 \choose 11}$; in this case, we really do not need to calculate all ${n(n + 1)}{2}$ entries in Pascal's triangle. Instead, we can can calculate the value by starting with the array {1, 1, 1, 1}, and then building from this the array {1, 2, 3, 4}, the {1, 3, 6, 10}, and repeating this nine more times produces the array {1, 12, 78, 364}, where ${14 \choose 11} = 364$. This is shown here:

How did we find the next entries in the array?

Suppose we are calculating ${14 \choose 5}$; again, in this case, we can calculate the value by starting with the array {1, 1, 1, 1, 1, 1}, and then building from this array the array {1, 2, 3, 4, 5, 6}, and then building from this the array {1, 3, 6, 10, 15, 21}, and repeating this seven more times produces the array {1, 10, 55, 220, 715, 2002}, where ${14 \choose 4} = 2002$. This is shown here:

Implement such a function and print all the binomial coefficients ${67 \choose k}$ for $k$ going from $0$ to $67$. Next, print all the binomial coefficients ${100 \choose k}$ for $k$ going from $0$ to $17$.

Question: Why are you not asked to calculate all binomial coefficients when $n = 68$ and why are you not asked to calculate the binomial coefficient ${100 \choose 18}$?

Question: What is the smallest reasonable array that you can use in your implementation? This author can implement it using an array of size k - 1 if $k \le \frac{n}{2}$.