题目描述：把 n 个骰子扔在地上，所有骰子朝上一面的点数之和为 s，输入 n，打印出 s 的所有可能的值的出现概率。
Solutions
这题目一看就很复杂，具体解析过程可参看，这里就不赘言了。一般遇到比较复杂的问题第一印象是将大问题分成很多小问题，那么如果找到比较明显的规律，可以采用递归的方式，这里第一种求解方法我们就用递归的方法。将：
class Solution:
# 假设在n个骰子和点数和Sum的情况下，组合的次数
def getNSumCount(self, n, n_sum):
if n < 1 or n_sum < n or n_sum > 6 * n:
return 0
if n == 1:
return 1
n_count = self.getNSumCount(n-1, n_sum-1) + self.getNSumCount(n-1, n_sum-2) + self.getNSumCount(n-1, n_sum-3) + self.getNSumCount(n-1, n_sum-4) + self.getNSumCount(n-1, n_sum-5) + self.getNSumCount(n-1, n_sum-6)
return n_count
# @param {int} n an integer
# @return {tuple[]} a list of tuple(sum, probability)
def dicesSum(self, n):
# Write your code here
if n is None or n <= 0:
return []
res = []
total = 0
for i in range(n, n*6+1):
n_count = self.getNSumCount(n, i)
total += n_count
res.append([i, n_count])
for i in range(6*n-n+1):
res[i] = [res[i][0], round(float(res[i][1]) / total, 2)]
return res
然而，这里采用递归方法有大量重复，比如在算 f(6, n_sum) 和 f(6, n_sum) 时会计算很多次 f(3, n_sum) 等。可以尝试采用迭代的方式进行修改：
class Solution:
# @param {int} n an integer
# @return {tuple[]} a list of tuple(sum, probability)
def dicesSum(self, n):
# Write your code here
if n == 0 : return None
result = [
[1,1,1,1,1,1],
]
# if n == 1: return result[0]
# 计算n个骰子出现的各个次数和
for i in range(1,n):
x = 5*(i+1)+1
result.append([0 for _ in range(x)])
for j in range(x):
if j < 6:
result[i][j] = (sum(result[i-1][0:j+1]))
elif 6 <= j <= 3*i+2:
result[i][j] = (sum(result[i-1][j-5:j+1]))
else:
break
left = 0
right = len(result[i]) - 1
while left <= right:
result[i][right] = result[i][left]
left += 1
right -= 1
res = result[-1]
all = float(sum(res))
other = []
# 第i个元素代表骰子总和为n+i
for i,item in enumerate(res):
pro = item/all
other.append([n+i,pro])
return other
看到现有的解法，复杂度似乎更多：
class Solution:
# @param {int} n an integer
# @return {tuple[]} a list of tuple(sum, probability)
def dicesSum(self, n):
# Write your code here
results = []
f = [[0 for j in xrange(6 * n + 1)] for i in xrange(n + 1)]
for i in xrange(1, 7):
f[1][i] = 1.0 / 6.0
for i in xrange(2, n + 1):
for j in xrange(i, 6 * n + 1):
for k in xrange(1, 7):
if j > k:
f[i][j] += f[i - 1][j - k]
f[i][j] /= 6.0
for i in xrange(n, 6 * n + 1):
results.append((i, f[n][i]))
return results