塞进裤子ヾ(≧O≦)〃嗷~

0%

剑指offer-60n个骰子的点数-python

《剑指offer》python实现系列,全目录

题目描述

把n个骰子扔在地上,所有骰子朝上一面的点数之和为s。输入n,打印出s的所有可能的值出现的概率。

1
2
3
输入:n = 1
输出:[[1, 0.17], [2, 0.17], [3, 0.17], [4, 0.17], [5, 0.17], [6, 0.17]]
解释:掷一次骰子,向上的数字和可能为1,2,3,4,5,6,出现的概率均为 0.17。
1
2
3
输入:n = 2
输出:[[2,0.03],[3,0.06],[4,0.08],[5,0.11],[6,0.14],[7,0.17],[8,0.14],[9,0.11],[10,0.08],[11,0.06],[12,0.03]]
解释:掷两次骰子,向上的数字和可能在[2,12],出现的概率是不同的。

剑指offer方法:

动态规划

n个骰子的点数和的最小值是n,最大值是6n,所有可能出现的情况为$6^n $ ,我们要做的是求点数之和出现的概率,计算

$$ \frac{count(sum=n)}{6^n} ,…, \frac{count(sum=6n)}{6^n} $$

现在我们考虑如何统计每个点数出现的次数。要想求出n个骰子的点数和,可以先把n个骰子分为两堆:第一堆只有一个:另一堆有n-1个。
单独的那一个有可能出现16的点数。我们需要计算16的每一种点数与剩下的n-1个骰子来计算点数之和。

动态规划

状态标识dp【n】【sum】,表示投掷完n个骰子后,点数之和sum出现的所有情况的次数,

$$ dp[n][sum] = dp[n-1][sum-1] +dp[n-1][sum-2]+ … + dp[n-1][sum-6] $$

单单看第n枚骰子,它的点数可能为 1, 2, 3, 4, 5, 6.因此投掷完 n 枚骰子后点数sum出现的次数,可以由投掷完n-1 枚骰子后,对应点数 sum-1, sum-2 ,…,sum−6 出现的次数之和转化过来。

初始状态位,$dp[1][1] = dp[1][2]=…=dp[1][6]=1$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# -*- coding:utf-8 -*-
class Solution:
def print_probability(self, n):
if n< 0:
return []
rows,cols = n+1,6*n+1 #保留0个骰子情况
dp = [[0 for i in range(cols)] for j in range(rows)]
#1个骰子时的初始值
for i in range(1,7):
dp[1][i] = 1
for i in range(2,n+1): #2到n个骰子时
for j in range(i,6*i+1):#可能出现的点数之和
for cur in range(1,6+1):
if j-cur<=0:
break
dp[i][j] += dp[i-1][j-cur]

res = []
allcount = pow(6,n)*1.0 #所有情况出现的次数,转成float
for i in range(n,6*n+1):
res.append(dp[n][i]/allcount)
return res


Solution().print_probability(2)

空间优化

每个阶段的状态都只和它前一阶段的状态有关,因此我们不需要用额外的一维来保存所有阶段。

f【2】【9】=f【1】【8】+f【1】【7】+f【1】【6】+。。。+f【1】【3】

f【2】【5】=f【1】【4】+f【1】【3】+f【1】【2】+f【1】【1】

f【2】【4】=f【1】【3】+f【1】【2】+f【1】【1】

简化成

f【sum】=f【sum-1】+f【sum-2】+ 。。。+f【sum-6】

用一维数组来保存一个阶段的状态,然后对下一个阶段可能出现的点数 j从大到小遍历,实现一个阶段到下一阶段的转换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
def print_probability(self, n):
if n< 0:
return []
cols = 6*n+1 #保留0个骰子情况
dp = [0 for i in range(cols)]
#1个骰子时的初始值
for i in range(1,7):
dp[i] = 1
for i in range(2,n+1):#2到n个骰子时
# for j in range(i,6*i+1,1):#可能出现的点数之和
for j in range(6*i,i-1,-1):#注意这里要从后往前算,
#如果从前往后算,计算do【3】使用的dp【2】是当前骰子的次数,不是n-1个骰子的次数
dp[j] = 0
for cur in range(1,6+1):
if j-cur<=0:
break
dp[j] += dp[j-cur]

res = []
allcount = pow(6,n)*1.0 #所有情况出现的次数,转成float
for i in range(n,6*n+1):
res.append(dp[i]/allcount)
return res

Re:
https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof/solution/nge-tou-zi-de-dian-shu-dong-tai-gui-hua-ji-qi-yo-3/

if help:小手一抖点个广告 or 大手一挥资助一下