这篇文章主要介绍LeetCode如何计算n个骰子的点数，文中介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们一定要看完！把n个骰子扔在地上，所有骰子朝上一面的点数之和为S。输入n，打印出S的所有可能的值出现的概率。假设骰子有face面，有n个骰子，那么总排列数就有faceⁿ个。（例如，有3个6面骰子，那么其总排列数为6=216个）。所有骰子的和最小值为n（假设骰子最小值为1），而和最大值为n * face(例如，有3个6面骰子，那么和最大值为18)， 那么就有 （n * face – n + 1）个可能和值，那么新建长度为（n * face – n + 1）的一维数组进行统计不同S出现的次数。然后骰子分别依次一个一个地投，并将其可能的值累加，最后将相应数组元素自增。最后，遍历数组，除以总排列数，得出结果。该算法时间复杂度为O(faceⁿ)，当n越大，运算时间越长。（n从12开始增大，等待时间就开始难以接受）空间复杂度为O(n * face)。确定问题解的表达式。可将f(n, s)表示n个骰子点数的和为s的排列情况总数确定状态转移方程。n个骰子点数和为s的种类数只与n-1个骰子的和有关。因为一个普通骰子有六个点数，那么第n个骰子可能出现1到6的点数。所以第n个骰子点数为1的话，f(n,s)=f(n-1,s-1)，当第n个骰子点数为2的话，f(n,s)=f(n-1,s-2)，…，依次类推。在n-1个骰子的基础上，再增加一个骰子出现点数和为s的结果只有这6种情况！那么有：上面就是状态转移方程，已知初始阶段的解为：当n=1时, f(1,1)=f(1,2)=f(1,3)=f(1,4)=f(1,5)=f(1,6)=1。该算法时间复杂度为O(n)，空间复杂度为O(n)。以3个6面骰子为例，所用到dp[i][j]数组如下图所示。由于每个dp[i][j]只于i-1时刻的状态有关，所以可以删去一个维度，简化算法。在上述解法的基础上，删去一个维度第二个循环从后往前遍历，避免覆盖以上是“LeetCode如何计算n个骰子的点数”这篇文章的所有内容，感谢各位的阅读！希望分享的内容对大家 香港云主机有帮助，更多相关知识，欢迎关注开发云行业资讯频道！
本篇内容介绍了“PHP中redis的使用方法”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！连接参数：ip、端口、连接超时时间，连接成功返回 true，否则返回 …
免责声明：本站发布的图片视频文字，以转载和分享为主，文章观点不代表本站立场，本站不承担相关法律责任；如果涉及侵权请联系邮箱：360163164@qq.com举报，并提供相关证据，经查实将立刻删除涉嫌侵权内容。
微信扫一扫 
