资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划,从策略到执行的一站式服务

Lintcode20DicesSumsolution题解

【题目描述】

成都创新互联成立于2013年,是专业互联网技术服务公司,拥有项目成都网站设计、成都网站建设网站策划,项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命,1280元盐城做网站,已为上家服务,为盐城各地企业和个人服务,联系电话:028-86922220

Throw n dices, the sum of the dices' faces is S. Given n, find the all possible value of S along with its probability.

Notice:You do not care about the accuracy of the result, we will help you to output results.

扔 n 个骰子,向上面的数字之和为 S。给定 Given n,请列出所有可能的 S 值及其相应的概率。

注意:你不用关注答案的准确性,我们会帮你输出答案

【题目链接】

http://www.lintcode.com/en/problem/dices-sum/

【题目解析】

这题用dfs做感觉更加直观,但是过不了time cost。换成dp的方法我是这么想的:

用dp[i][j]表示有i + 1个骰子的情况下,掷到的和为j的次数。那么intialize这个dp[0][j], j = 1...6的值都为1,然后从i = 1开始做循环。i个骰子和i + 1个骰子的差别就是1个骰子(废话),所以再用一个k = 1...6进行遍历,那么i + 1个骰子掷到j + k的次数就是原来dp[i][j + k]的次数加上dp[i - 1][j]。

这样我们就求得了n个骰子的情况下,每个S出现的次数dp[n - 1][j], j = n...6 * n。那么概率就是每个dp[n - 1][j]除以出现的总次数sum(dp[n - 1][j]).

这里要注意dp的值可能很大,所以要用到long long,否则在有些test case(e.g., n = 15)的情况下,会出现负数答案。

【答案链接】

http://www.jiuzhang.com/solution/dices-sum/


文章名称:Lintcode20DicesSumsolution题解
标题路径:http://www.cdkjz.cn/article/jhchco.html
多年建站经验

多一份参考,总有益处

联系快上网,免费获得专属《策划方案》及报价

咨询相关问题或预约面谈,可以通过以下方式与我们联系

大客户专线   成都:13518219792   座机:028-86922220