首页 > 其他分享 >剑指 Offer 60. n个骰子的点数

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

时间:2023-09-07 22:03:09浏览次数:38  
标签:骰子 Offer int double 60 ++ length 0.16667 dp

把n个骰子扔在地上,所有骰子朝上一面的点数之和为s。输入n,打印出s的所有可能的值出现的概率。

 

你需要用一个浮点数数组返回答案,其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。

 

示例 1:

输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]

示例 2:

输入: 2
输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]



感觉难点在于怎么表达不可能的情况。
class Solution {
    public double[] dicesProbability(int n) {
        double[][] dp = new double[n][6 * n + 1];
        for (int i = 1; i < 7; i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i < n; i++) {
            for (int j = i; j <= 6 * n; j++) {
                for (int k = 0; k < 6; k++) {
                    if (j - k - 1 >= 0 && dp[i - 1][j - k - 1] != 0) {
                        dp[i][j] += dp[i - 1][j - k - 1];
                    }
                }
            }
        }
        double total = 0;
        for (int i = 0; i < dp[0].length; i++) {
            total += dp[dp.length - 1][i];
        }
        for (int i = 0; i < dp[0].length; i++) {
            dp[dp.length - 1][i] /= total;
        }
        return Arrays.copyOfRange(dp[dp.length - 1], n, dp[dp.length - 1].length);
    }
}

标签:骰子,Offer,int,double,60,++,length,0.16667,dp
From: https://blog.51cto.com/u_15862486/7402038

相关文章

  • 剑指 Offer 60. n个骰子的点数
    把n个骰子扔在地上,所有骰子朝上一面的点数之和为s。输入n,打印出s的所有可能的值出现的概率。 你需要用一个浮点数数组返回答案,其中第i个元素代表这n个骰子所能掷出的点数集合中第i小的那个的概率。 示例1:输入:1输出:[0.16667,0.16667,0.16667,0.16667,0.16667,0.16667......
  • 剑指 Offer 22. 链表中倒数第k个节点
    输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。例如,一个链表有6个节点,从头节点开始,它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。示例:给定一个链表:1->2->3->4->5,和k=......
  • 统信UOS1060使用UDOM工具箱打开支持长文件名特性
    原文链接:统信UOS1060使用UDOM工具箱打开支持长文件名特性hello,大家好啊,今天给大家带来一篇文章,在统信UOS发布的最新版桌面操作系统1060中,增加了长文件名模式,最长支持255个中文或英文字符,这样对于在windows上使用长文件的文件,迁移到国产操作系统上而言,避免了文件命名失败、文件丢失......
  • CF 1860 B
    FancyCoins这道题使用贪心。先使用a1个常规硬币,补足m%k的金额,不够的使用花色硬币补上,并最大化a1硬币的价值。再计算剩余需要价值为k的硬币数量,不够的使用花色硬币补足,并输出总共使用的花色硬币数量。代码#include<bits/stdc++.h>#defineendl'\n'usingnamespacestd;ty......
  • CF 1860 C【最大上升子序列】
    C.GameonPermutation这道题需要求出先手必胜点通过分析可知,每个位置结尾的最大上升子序列长度为2的点为先手必胜点,≥3的点为先手必败点。即只需要求出以每个位置为结尾的最大上升子序列长度为2的点的数量即可求出答案。本题目的n(1≤n≤3⋅105),所以无法使用O(n2)的方法,因此......
  • 剑指 Offer 46. 把数字翻译成字符串
    题目链接:剑指Offer46.把数字翻译成字符串题目描述:解法思路:代码://dp[i]=dp[i-1]+dp[i-2]//dp[i]表示长度为i的数字,翻译成字符串有多少种functranslateNum(numint)int{s:=strconv.Itoa(num)n:=len(s)dp:=make([]int,n+1)dp[0]=1......
  • 剑指Offer
    题目链接:题目描述:解法思路:代码:funcfindNthDigit(nint)int{//1、确定是几位数(-10-90-900-9000等)//2、确定是几位数的第几位数(求第n位数是属于哪一个数的)//3、确定是属于那个数的第几位digit,digitNum,count:=1,1,9//digit表示是几位数;dig......
  • 剑指Offer 43. 1~n 整数中 1 出现的次数
    题目链接:剑指Offer43.1~n整数中1出现的次数题目描述:解法思路:代码:funccountDigitOne(nint)int{ //思路 ifn==0{ return0 } //求出该数的各个位上的数字,保存到nums中 varnums[]int tmp:=n fortmp!=0{ a:=tmp%10 nums=append(nums,a)......
  • lattice crosslink开发板mipi核心板csi测试dsi屏lif md6000 fpga
    1.概述    CrossLink开发板,是用Lattice的芯片CrossLink家族系列的,LIF-MD6000-6JM80I。该芯片用于桥接视频接口功能,自带2路MIPI硬核的功能,4LANE MIPI的功能,支持高速率1.5Gbps。   其他普通IO支持1.2Gbps速率,支持5路MIPI通道功能。 芯片包含LVDS,SLVS200,SubLV......
  • 用友畅捷通T+ Upload.aspx任意文件上传漏洞CNVD-2022-60632
    漏洞描述用友畅捷通T+Upload.aspx接口存在任意文件上传漏洞,攻击者通过preload参数绕过身份验证进行文件上传,控制服务器漏洞影响用友畅捷通T+漏洞复现fofa语法:app="畅捷通-TPlus"登录页面如下:上传文件类型验证不完善,可上传任意文件到服务器中的任意位置,验证POCPOST/......