建站
咨詢
售后
建站咨詢
新聞中心
【題目描述】
成都創(chuàng)新互聯(lián)成立于2013年，是專業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項(xiàng)目成都網(wǎng)站設(shè)計(jì)、成都網(wǎng)站建設(shè)網(wǎng)站策劃，項(xiàng)目實(shí)施與項(xiàng)目整合能力。我們以讓每一個(gè)夢(mèng)想脫穎而出為使命，1280元鹽城做網(wǎng)站,已為上家服務(wù),為鹽城各地企業(yè)和個(gè)人服務(wù),聯(lián)系電話: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 個(gè)骰子，向上面的數(shù)字之和為 S。給定 Given n，請(qǐng)列出所有可能的 S 值及其相應(yīng)的概率。
注意:你不用關(guān)注答案的準(zhǔn)確性，我們會(huì)幫你輸出答案
【題目鏈接】
http://www.lintcode.com/en/problem/dices-sum/
【題目解析】
這題用dfs做感覺更加直觀，但是過(guò)不了time cost。換成dp的方法我是這么想的：
用dp[i][j]表示有i + 1個(gè)骰子的情況下，擲到的和為j的次數(shù)。那么intialize這個(gè)dp[0][j], j = 1...6的值都為1，然后從i = 1開始做循環(huán)。i個(gè)骰子和i + 1個(gè)骰子的差別就是1個(gè)骰子（廢話），所以再用一個(gè)k = 1...6進(jìn)行遍歷，那么i + 1個(gè)骰子擲到j(luò) + k的次數(shù)就是原來(lái)dp[i][j + k]的次數(shù)加上dp[i - 1][j]。
這樣我們就求得了n個(gè)骰子的情況下，每個(gè)S出現(xiàn)的次數(shù)dp[n - 1][j], j = n...6 * n。那么概率就是每個(gè)dp[n - 1][j]除以出現(xiàn)的總次數(shù)sum(dp[n - 1][j]).
這里要注意dp的值可能很大，所以要用到long long，否則在有些test case（e.g., n = 15）的情況下，會(huì)出現(xiàn)負(fù)數(shù)答案。
【答案鏈接】
http://www.jiuzhang.com/solution/dices-sum/
網(wǎng)站標(biāo)題：Lintcode20DicesSumsolution題解
分享網(wǎng)址：http://fisionsoft.com.cn/article/jhchco.html
