題目：

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

骰子一共有6個(gè)面，每個(gè)面上都有一個(gè)點(diǎn)數(shù)，對(duì)應(yīng)的是1~6之間的數(shù)字。所以n個(gè)骰子的點(diǎn)數(shù)和的最小值為n，最大值為6n.另外，根據(jù)排列組合的知識(shí)，我們還知道n個(gè)骰子的所有點(diǎn)數(shù)的排列數(shù)位6^{n。要解決這個(gè)問(wèn)題，我們需要先統(tǒng)計(jì)出每個(gè)點(diǎn)數(shù)出現(xiàn)的次數(shù)，然后把每個(gè)點(diǎn)數(shù)出現(xiàn)的次數(shù)除以6}n，就能求出每個(gè)點(diǎn)數(shù)出現(xiàn)的概率。

思路一：基于遞歸求骰子點(diǎn)數(shù)，時(shí)間效率不夠高

現(xiàn)在我們考慮如何統(tǒng)計(jì)每個(gè)點(diǎn)數(shù)出現(xiàn)的次數(shù)。要想求出n個(gè)骰子的點(diǎn)數(shù)和，可以先把n個(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è)骰子。

我們可以定義一個(gè)長(zhǎng)度位6n-n+1的數(shù)組，將和為s的點(diǎn)數(shù)出現(xiàn)的次數(shù)保存到數(shù)組的第s-n個(gè)元素里

python代碼如下：

class Solution:

    def PrintProb(self, n):
        if n <1:
            return
        g =6
        maxSum =n *g
        pProb =[0]*(maxSum -n +1)
        self.Prob(n, pProb)
        total =6**n
        for i in range(n, maxSum+1):
            ratio =pProb[i-n]/total
            print(i,': ',ratio)
            
    def Prob(self, n, pProb):
        g =6
        for i in range(1, g+1):
            self.Prob2(n, n, i, pProb)
            
    def Prob2(self, ori, cur, sum, pProb):
        g =6
        if cur ==1:
            pProb[sum -ori] +=1
        else:
            for i in range(1, g+1):
                self.Prob2(ori, cur-1, i+sum, pProb)

思路二：動(dòng)態(tài)規(guī)劃

1. 現(xiàn)在變量有：骰子個(gè)數(shù)，點(diǎn)數(shù)和。當(dāng)有c個(gè)骰子，點(diǎn)數(shù)和為k時(shí)，出現(xiàn)次數(shù)記為dp(c, k)。那與c-1各骰子階段之間的關(guān)系是怎樣的？

2. 當(dāng)我有c-1個(gè)骰子時(shí)，再增加一個(gè)骰子，這個(gè)骰子的點(diǎn)數(shù)只可能為1、2、3、4、5或6，則有：

   • (c-1, k-1)：第c個(gè)骰子投了點(diǎn)數(shù)1

   • (c-1, k-2)：第c個(gè)骰子投了點(diǎn)數(shù)2

   • ……

   • (c-1, k-6)：第c個(gè)骰子投了點(diǎn)數(shù)6

   在c-1個(gè)骰子的基礎(chǔ)上，再增加一個(gè)骰子出現(xiàn)點(diǎn)數(shù)和為k的結(jié)果只有這6種情況，所以：

   dp(c, k) =dp(c-1, k-1) +dp(c-1, k-2) +dp(c-1, k-3) +dp(c-1, k-4) +dp(c-1, k-5) +dp(c-1, k-6)（注意當(dāng)k<6的處理越界問(wèn)題）

3. 有一個(gè)骰子：

   dp(1, 1) =dp(1, 2) =dp(1, 3) =dp(1, 4) =dp(1, 5) =dp(1, 6) =1

   因此狀態(tài)轉(zhuǎn)移方程為：

   dp(c)(k) =sum(dp(c-1)(k-m))(1<=m<=g and m<k)

def get_ans(n):
    if n<1:
        return
    total =6**n
    dp =[[0 for i in range(6*n+1)] for j in range(n+1) ]
    for i in range(1,7):
        dp[1][i] =1
    
    for i in range(2, n+1):
        for j in range(2, 6*n+1):
            sum =0
            
            for m in range(1, j):
                if m <=6:
                    sum +=dp[i-1][j-m]
            dp[i][j] =sum
            
    for k in range(n, 6*n+1):
        print(k, ': ', dp[n][k]/total)

更多精彩，關(guān)注“咋家”