題目：把n個(gè)骰子扔在地上，所有骰子朝上一面的點(diǎn)數(shù)之和為S。輸入n，打印出S的所有可能的值出現(xiàn)的概率。

分析：骰子一共6個(gè)面，每個(gè)面上都有一個(gè)點(diǎn)數(shù)，對(duì)應(yīng)的數(shù)字是1到 6之間的一個(gè)數(shù)字。所以，n個(gè)骰子的點(diǎn)數(shù)和的最小值為n，最大值為6n。因此，一個(gè)直觀的思路就是定義一個(gè)長(zhǎng)度為6n-n的數(shù)組，和為S的點(diǎn)數(shù)出現(xiàn)的次數(shù)保存到數(shù)組第S-n個(gè)元素里。另外，我們還知道n個(gè)骰子的所有點(diǎn)數(shù)的排列數(shù)6^n。一旦我們統(tǒng)計(jì)出每一點(diǎn)數(shù)出現(xiàn)的次數(shù)之后，因此只要把每一點(diǎn)數(shù)出現(xiàn)的次數(shù)除以n^6，就得到了對(duì)應(yīng)的概率。

該思路的關(guān)鍵就是統(tǒng)計(jì)每一點(diǎn)數(shù)出現(xiàn)的次數(shù)。要求出n個(gè)骰子的點(diǎn)數(shù)和，我們可以先把n個(gè)骰子分為兩堆：第一堆只有一個(gè)，另一個(gè)有n-1個(gè)。單獨(dú)的那一個(gè)有可能出現(xiàn)從1到6的點(diǎn)數(shù)。我們需要計(jì)算從1到6的每一種點(diǎn)數(shù)和剩下的n-1個(gè)骰子來(lái)計(jì)算點(diǎn)數(shù)和。接下來(lái)把剩下的n-1個(gè)骰子還是分成兩堆，第一堆只有一個(gè)，第二堆有n-2個(gè)。我們把上一輪那個(gè)單獨(dú)骰子的點(diǎn)數(shù)和這一輪單獨(dú)骰子的點(diǎn)數(shù)相加，再和剩下的n-2個(gè)骰子來(lái)計(jì)算點(diǎn)數(shù)和。分析到這里，我們不難發(fā)現(xiàn)，這是一種遞歸的思路。遞歸結(jié)束的條件就是最后只剩下一個(gè)骰子了。

基于這種思路，我們可以寫(xiě)出如下代碼：

int?g_maxValue=6;

void?SubProbabilityofDices(int?original,?int?current,?int?value,?int?tempSum,?int?*pProbalities)
{
	if(current==1)
	{
		int?sum=value+tempSum;
		pProbalities[sum-original]++;
	}
	else
	{
		for(int?i=1;?i<=g_maxValue;?i++)
		{
			int?sum=value+tempSum;
			SubProbabilityofDices(original,?current-1,?i,?sum,?pProbalities);
		}
	}
}

void?SumProbabilityofDices(int?number,?int*?pProbabilities)
{
	for(int?i=1;?i<=g_maxValue;?i++)//第一個(gè)骰子
		SubProbabilityofDices(number,?number,?i,?0,?pProbabilities);

}

void?PrintSumProbabilityofDices_1(int?number)
{
	if(number<1)
		return;

	int?maxSum=number*g_maxValue;
	int*?pProbabilities=new?int?[maxSum-number+1];
	for(int?i=number;?i<=maxSum;?i++)
		pProbabilities[i-number]=0;

	SumProbabilityofDices(number,?pProbabilities);

	int?total=pow((double)g_maxValue,?number);
	for(i=number;?i<=maxSum;?i++)
	{
		float?ratio=(float)pProbabilities[i-number]/total;
		cout<<i<<":"<<ratio<<endl;
	}
	delete[]?pProbabilities;
}

上述算法當(dāng)number比較小的時(shí)候表現(xiàn)很優(yōu)異。但由于該算法基于遞歸，它有很多計(jì)算是重復(fù)的，從而導(dǎo)致當(dāng)number變大時(shí)性能讓人不能接受。

為了避免遞歸時(shí)的重復(fù)計(jì)算，我們很自然聯(lián)想到動(dòng)態(tài)規(guī)劃（DP）。用表格法，一行代表一個(gè)骰子，列表示各個(gè)S值，所以一共有6*N列。本來(lái)是要用N行的，可是這里只用了一個(gè)二維的數(shù)組，因?yàn)楝F(xiàn)在計(jì)算的值只與前一次計(jì)算的值相關(guān)，所以其中一行保存上一次計(jì)算的結(jié)果，另一行保存正在計(jì)算的結(jié)果，這樣可以節(jié)省大量的空間。我們可以考慮用兩個(gè)數(shù)組來(lái)存儲(chǔ)骰子點(diǎn)數(shù)每一總數(shù)出現(xiàn)的次數(shù)。在一次循環(huán)中，第一個(gè)數(shù)組中的第n個(gè)數(shù)字表示骰子和為n出現(xiàn)的次數(shù)。那么在下一循環(huán)中，我們加上一個(gè)新的骰子。那么此時(shí)和為n的骰子出現(xiàn)的次數(shù)，應(yīng)該等于上一次循環(huán)中骰子點(diǎn)數(shù)和為n-1、n-2、n-3、n-4、n-5與n-6的總和。所以我們把另一個(gè)數(shù)組的第n個(gè)數(shù)字設(shè)為前一個(gè)數(shù)組對(duì)應(yīng)的第n-1、n-2、n-3、n-4、n-5與n-6之和。

void?PrintSumProbabilityofDices_2(int?number)
{
	double*?pProbabilities[2];
	pProbabilities[0]=new?double[number*g_maxValue+1];
	pProbabilities[1]=new?double[number*g_maxValue+1];

	for(int?i=0;?i<number*g_maxValue+1;?i++)
	{
		pProbabilities[0][i]=0;
		pProbabilities[1][i]=0;
	}

	int?flag=0;
	for(i=1;?i<=g_maxValue;?i++)
		pProbabilities[flag][i]=1;

	for(int?k=2;?k<=number;?k++)
	{
		for(int?i=k;?i<=g_maxValue*k;?i++)
		{
			pProbabilities[1-flag][i]=0;
			for(int?j=1;?j<=i?&&?j<=g_maxValue;?j++)
				pProbabilities[1-flag][i]+=pProbabilities[flag][i-j];
		}
		flag=1-flag;
	}

	double?total=pow((double)g_maxValue,?number);

	for(i=number;?i<=g_maxValue*number;?i++)
	{
		double?ratio=pProbabilities[flag][i]/total;
		cout<<i<<":"<<ratio<<endl;
	}

	delete[]?pProbabilities[0];
	delete[]?pProbabilities[1];
}