栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

Java n个骰子

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

Java n个骰子

剑指offer 60.n个骰子的点数

解题思路;
dp[i][j]: 表示i个骰子时, 摇到和为j的概率
k: 表示摇到骰子的点数
dp[1][k]: 表示一个骰子时, 可能会摇到和为1, 2, 3, 4, 5, 6, 所以k取1~6, 被摇到的点数概率都为1/6
dp[i - 1][j - k]: 表示当i个骰子里就减去一个的时候, 摇到的和就为j - k
从而可以得dp[i][j] = dp[i - 1][j - k]*dp[1][k]

当有n个骰子时:
骰子和的取值范围: [n, 6n]
骰子和出现的种类: 6n - n + 1 = 5n + 1

例如: 有两个骰子
和: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
可以从上观察得: 和出现的种类为 11 种

class Solution {
    public double[] dicesProbability(int n) {
        if(n <= 0) return new double[0];
        double[][] dp = new double[n + 1][6 * n + 1];
        for(int i = 1; i <= 6; i++){
            dp[1][i] = (double) 1 / 6;
        }
        //i表示骰子个数
        //j表示骰子和
        //k取值是1 ~ 6
        for(int i = 2; i <= n; i++){
            int maxValue = 6 * i;
            for(int j = i; j <= maxValue; j++){
                for(int k = 1; k <= 6; k++){
                    if(j - k <= 0){
                        continue;
                    }
                    dp[i][j] += dp[1][k] * dp[i - 1][j - k];
                }
            }
        }
        double[] res = new double[5 * n + 1];
        int value = n;
        for(int i = 0; i < res.length; i++){
            res[i] = dp[n][value++];
        }
        return res;
    }
}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/959597.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号