题目：
把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
骰子一共有6个面，每个面上都有一个点数，对应的是1~6之间的数字。所以n个骰子的点数和的最小值为n，最大值为6n.另外，根据排列组合的知识，我们还知道n个骰子的所有点数的排列数位6n。要解决这个问题，我们需要先统计出每个点数出现的次数，然后把每个点数出现的次数除以6n，就能求出每个点数出现的概率。
思路一：基于递归求骰子点数，时间效率不够高
现在我们考虑如何统计每个点数出现的次数。要想求出n个骰子的点数和，可以先把n个骰子分为两堆：第一堆只有一个；另一堆有n-1个。单独的那一个有可能出现16的点数。我们需要计算16的每一种点数和剩下的n~1个骰子来计算点数和。接下来把剩下的n-1个骰子仍然分成两堆：第一堆只有一个；第二堆有n-2个。我们把上一轮那个单独骰子的点数和这一轮单独骰子的点数和相加，再和剩下的n-2个骰子来计算点数和。分析到这里，我们不难发现这是一种递归的思路，递归结束的条件就是最后只剩下一个骰子。
我们可以定义一个长度位6n-n+1的数组，将和为s的点数出现的次数保存到数组的第s-n个元素里
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)
思路二：动态规划
-
现在变量有：骰子个数，点数和。当有c个骰子，点数和为k时，出现次数记为dp(c, k)。那与c-1各骰子阶段之间的关系是怎样的？
-
当我有c-1个骰子时，再增加一个骰子，这个骰子的点数只可能为1、2、3、4、5或6，则有：
-
(c-1, k-1)：第c个骰子投了点数1
-
(c-1, k-2)：第c个骰子投了点数2
-
……
-
(c-1, k-6)：第c个骰子投了点数6
在c-1个骰子的基础上，再增加一个骰子出现点数和为k的结果只有这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)（注意当k<6的处理越界问题）
-
-
有一个骰子：
dp(1, 1) =dp(1, 2) =dp(1, 3) =dp(1, 4) =dp(1, 5) =dp(1, 6) =1
因此状态转移方程为：
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)
更多精彩，关注“咋家”
网友评论