LintCode : Dices Sum 骰子求和

悠悠 2021-06-24 16:10 448阅读 0赞

**试题：**  
Throw n dices, the sum of the dices’ faces is S. Given n, find the all possible value of S along with its probability.

Example  
Example 1:

Input: n = 1  
Output: \[\[1, 0.17\], \[2, 0.17\], \[3, 0.17\], \[4, 0.17\], \[5, 0.17\], \[6, 0.17\]\]  
Explanation: Throw a dice, the sum of the numbers facing up may be 1, 2, 3, 4, 5, 6, and the probability of each result is 0.17.  
Notice  
You do not care about the accuracy of the result, we will help you to output results.  
**代码：**  
有三个未知数：扔骰子次数，在当前次数上和的取值范围，当前次扔骰子可能出现的点数。

public class Solution {
        /**
         * @param n an integer
         * @return a list of Map.Entry<sum, probability>
         */
        public List<Map.Entry<Integer, Double>> dicesSum(int n) {
            // Write your code here
            // Ps. new AbstractMap.SimpleEntry<Integer, Double>(sum, pro)
            // to create the pair
            long[][] dp = new long[n+1][6*n+1];
            for(int i=1; i<=6; i++){
                dp[1][i] = 1;
            }
            
            for(int i=2; i<=n; i++){
                for(int j=i; j<=6*i; j++){
                    for(int k=1; k<=6&&k<=j; k++){
                        dp[i][j] = dp[i][j] + dp[i-1][j-k];
                    }
                }
            }
            
            double total = Math.pow(6,n);
            HashMap map = new HashMap<Integer,Double>();
            for(int i=n; i<=6*n; i++){
                map.put(i,dp[n][i]/total);
            }
            
            return new ArrayList<Map.Entry<Integer,Double>>(map.entrySet());
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，448人围观）

还没有评论，来说两句吧...

相关阅读

相关 Leetcode-1155 Number of Dice Rolls With Target Sum(掷骰子的N种方法)

dp\[i\]\[j\]表示前i个骰子到达数字总和j的方案数 dp\[i\]\[j\] = Σdp\[i-1\]\[j-k\]，其中k是一个骰子能掷出的范围 1 d

「爱情、让人受尽委屈。」/ 2023年06月01日 08:47/ 0 赞/ 1 阅读

相关【LintCode 简单】167. 链表求和

1.问题描述：你有两个用链表代表的整数，其中每个节点包含一个数字。数字存储按照在原来整数中`相反`的顺序，使得第一个数字位于链表的开头。写出一个函数将两个整数相加，用链表形

浅浅的花香味﹌/ 2022年11月28日 13:28/ 0 赞/ 105 阅读

相关 case when求和用SUM

SELECT CITY, COUNT( ) ins, SUM( CASE WHEN OUT_TIME IS NOT NULL THEN

我就是我/ 2022年10月27日 13:59/ 0 赞/ 222 阅读

相关 Elasticsearch根据查询条件求和sum

一、概述现有news表，数据存放在Elasticsearch中。需要根据关键字查询之后，sum计算点击数。数据如下： { "conten

缺乏、安全感/ 2022年10月13日 12:45/ 0 赞/ 201 阅读

相关 3个骰子求和

给定一个整数，3至18，求3个骰子累加之和为这个整数，打印出这三个骰子各自显示的数 // 3RandomSum.cpp : 定义控制台应用程序的入口点。

超、凢脫俗/ 2022年08月18日 00:42/ 0 赞/ 166 阅读

相关避免mybatis SUM求和返回null

<select id="getOrderSumMoneyByUserCode" parameterType="string" resultType="bigD

女爷i/ 2022年06月09日 08:24/ 0 赞/ 279 阅读

相关 EOS骰子游戏dice.cpp程序源码

/ @file @copyright defined in eos/LICENSE.txt / include <util

矫情吗；*/ 2022年05月08日 01:20/ 0 赞/ 188 阅读

相关 [HEOI2016]求和 sum

\[HEOI2016\]求和 sum 标签： NTT cdq分治多项式求逆第二类斯特林数 -------------------- Description

忘是亡心i/ 2021年09月29日 10:54/ 0 赞/ 281 阅读

相关 LintCode: Combination Sum

一个数可以使用多次图：　　节点：x（当前的和，当前要考虑的数a\[i\]）　　边：x-> 　　　　y1（当前的和，下一个要考虑的数a\[i+1\]）　　　　y

清疚/ 2021年09月19日 09:46/ 0 赞/ 181 阅读

相关 LintCode : Dices Sum 骰子求和

试题： Throw n dices, the sum of the dices’ faces is S. Given n, find the all possible va

悠悠/ 2021年06月24日 16:10/ 0 赞/ 449 阅读