【題目描述】

成都創(chuàng)新互聯(lián)公司是一家專業(yè)從事網(wǎng)站建設(shè)、網(wǎng)絡(luò)營(yíng)銷、小程序定制開(kāi)發(fā)、網(wǎng)站運(yùn)營(yíng)為一體的建站企業(yè)；在網(wǎng)站建設(shè)告別千篇一律，告別似曾相識(shí)，這一次我們重新定義網(wǎng)站建設(shè)，讓您的網(wǎng)站別具一格。自適應(yīng)網(wǎng)站建設(shè)，實(shí)現(xiàn)全網(wǎng)營(yíng)銷！一站適應(yīng)多終端，一樣的建站，不一樣的體驗(yàn)！

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做感覺(jué)更加直觀，但是過(guò)不了time cost。換成dp的方法我是這么想的：

用dp[i][j]表示有i + 1個(gè)骰子的情況下，擲到的和為j的次數(shù)。那么intialize這個(gè)dp[0][j], j = 1...6的值都為1，然后從i = 1開(kāi)始做循環(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/

文章名稱：Lintcode20DicesSumsolution題解-創(chuàng)新互聯(lián)
當(dāng)前鏈接：http://chinadenli.net/article32/ephsc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供ChatGPT、商城網(wǎng)站、建站公司、外貿(mào)網(wǎng)站建設(shè)、企業(yè)建站、網(wǎng)站營(yíng)銷

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)