二項式的計算

一共有兩種方法：

1）遞歸調用

2）動态規劃

1)遞歸調用

int bino1(int n, int r)//二項式的遞歸求法
{
	if (r == 0 || r == n)
		return 1;
	return bino1(n - 1, r - 1) + bino1(n - 1, r);

}
           

2)利用動态規劃

int dp[1000][1000];
const int M = 100000000000 + 100;
           

int bino2(int n, int r)//利用動态規劃
{
	memset(dp, 0, sizeof(dp));
	if (r == 0 || r == n)
	{
		return 1;
	
	}
	if (dp[n][r] != 0)
	{
	
		return dp[n][r];
	}
	return dp[n][r] = min(bino2(n - 1, r - 1) + bino2(n - 1, r),M);//這裡取最小值是因為：C(200,100)大概是900兆，遠超過int的取值範圍

}