面试题60:n个骰子的点数

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

思路:
这道题需要用到动态规划,首先需要确定初始边界条件,当n等于1时,1-6出现的次数均为1;接着确定状态转换过程,当增加一个骰子时,第n个骰子的可能结果为1-6,所以出现次数为n的结果的次数为上一维度n-1,n-2,n-3,n-4,n-5,n-6的次数之和,且新增一个骰子可能出现的次数为n~6n;

代码思路:

class Solution:
    def twoSum(self, n: int) -> List[float]:
        #一维数组
        res = [0]*(6*n+1)
        for i in range(1,7):
            res[i] = 1   #初始条件
        for i in range(2,n+1):   #骰子个数递增
            for j in range(6*i,i-1,-1):  #倒着赋值 否则会覆盖
                temp = 0
                for k in range(1,7):
                    if j-k<i-1:  #特殊情况
                        break
                    temp +=res[j-k]   #6次计算
                res[j] = temp
        total = 6**n
        return [x/total for x in res[n:]]

提交结果:

image.png
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容