Geeks 面试题：Binomial Coefficient

Binomial Coefficient

Following are common definition of Binomial Coefficients.
1) A binomial coefficient C(n, k) can be defined as the coefficient of X^k in the expansion of (1 + X)^n.

2) A binomial coefficient C(n, k) also gives the number of ways, disregarding order, that k objects can be chosen from among n objects; more formally, the number of k-element subsets (or k-combinations) of an n-element set.

The Problem
Write a function that takes two parameters n and k and returns the value of Binomial Coefficient C(n, k).For example, your function should return 6 for n = 4 and k = 2, and it should return 10 for n = 5 and k = 2.

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

http://www.geeksforgeeks.org/dynamic-programming-set-9-binomial-coefficient/

要清楚计算方法，然后一步一步计算，注意画好表。

下面是动态规划法和递归法。

其中第二个程序是最省内存的方法了。

比如计算C(n,k) = C(10,8)其实C(10,8) = C(10,2)那么就可以利用这个特性，进一步优化空间有8个空间变成2个空间，而且循环也有10*8成了10*2，最省内存和最优化的方法了。

// A space optimized Dynamic Programming Solution
int binomialCoeffDPSaveSpace(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;
}

int binomialCoDPSaveSpace(int n, int k)
{
	k = min(k,n-k);
	vector<int> ta(k+1);
	ta[0] = 1;
	for (int i = 0; i <= n; i++)
	{
		for (int j = min(i,k); j > 0 ; j--)
		{
			ta[j] = ta[j] +ta[j-1];
		}
	}
	return ta[k];
}

// Returns value of Binomial Coefficient C(n, k)
int binomialCoeff(int n, int k)
{
	// Base Cases
	if (k==0 || k==n)
		return 1;

	// Recur
	return  binomialCoeff(n-1, k-1) + binomialCoeff(n-1, k);
}

int main()
{
	int n = 10, k = 8;
	printf("Value of C(%d, %d) is %d\n ", n, k, binomialCoeff(n, k));

	cout<<binomialCoDPSaveSpace(n, k)<<endl;

	system("pause");
	return 0;
}