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

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

时间:2023-04-15 16:25:02浏览次数:47  
标签:tmp 骰子 Offer int 复杂度 60 dp

题目链接:剑指 Offer 60. n个骰子的点数

方法:动态规划

解题思路

  • \(n = 1\) 时可能的和为 \([1, 6]\),其概率为 \(dp[1][] = [1/6, 1/6, 1/6, 1/6, 1/6, 1/6]\)
  • \(n = 2\) 时对于第一个骰子为 \(1\) 时,第二个骰子可以为 \([1, 6]\),其可以构成的和为 \([2, 7]\),分别为其中的和 \([i + j]\) 增加 \(dp[1][i] / 6\) 的概率,即 \(dp[2][i + j] += dp[1][i] / 6\),其中 \(i = 1\),表示第一个骰子为 \(1\),\(j\) 为第二个骰子的值可以取 \([1, 6]\);
  • ...
  • 由于每一层的 \(dp\) 数组的值只和上一层有关,因此可以优化为一维数组实现。

代码

class Solution {
public:
    vector<double> dicesProbability(int n) {
        vector<double> dp(6, 1.0 / 6.0);
        for (int i = 2; i <= n; i ++ ) {
            vector<double> tmp(5 * i + 1, 0);
            for (int j = 0; j < dp.size(); j ++ ) {
                for (int k = 0; k < 6; k ++ ) {
                    tmp[j + k] += dp[j] / 6.0;
                }
            }
            dp = tmp;
        }
        return dp;
    } 
};

复杂度分析

时间复杂度:\(O(n^2)\);
空间复杂度:\(O(n)\)。

标签:tmp,骰子,Offer,int,复杂度,60,dp
From: https://www.cnblogs.com/lxycoding/p/17321308.html

相关文章

  • 龙芯3a6000相当于英特尔什么水平
    国产芯片在近几年都是非常优秀的,而最近新爆料的龙芯3a6000马上就要出现了,他相当于AMDzen3和英特尔11代酷睿的水平,这也是达到了一个很高的水平了。龙芯3a6000相当于英特尔什么水平:答:11代酷睿龙芯3a6000相当于英特尔的11代酷睿的水平,还是拥有非常高的水平的。龙芯3a6000同样的也......
  • 1650显卡和1060比较
    1060显卡可以被称之为最有性价比的显卡了,我们到现在还可以使用这些显卡去游玩很多游戏,而作为后出的1650显卡他的性能又是如何呢,我们今天就来比较一下。1650显卡和1060比较:1、游戏性能在游戏性能这方面两款显卡都差不多,不过1060的核心时钟速度要比1650好,所以在游戏纹理映射方面......
  • 【剑指 Offer 】14- I. 剪绳子
    【题目】给你一根长度为n的绳子,请把绳子剪成整数长度的m段(m、n都是整数,n>1并且m>1),每段绳子的长度记为k[0],k[1]...k[m-1]。请问k[0]*k[1]*...*k[m-1]可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。示例1:输入:......
  • 【剑指 Offer】 66. 构建乘积数组
    【题目】给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B[i]的值是数组A中除了下标i以外的元素的积,即B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。示例:输入:[1,2,3,4,5]输出:[120,60,40,30,24]来源:力扣(LeetCode)链接:https://leetc......
  • leetcode-1360-easy
    NumberofDaysBetweenTwoDatesWriteaprogramtocountthenumberofdaysbetweentwodates.Thetwodatesaregivenasstrings,theirformatisYYYY-MM-DDasshownintheexamples.Example1:Input:date1="2019-06-29",date2="201......
  • 用 Go 剑指 Offer 56 - I. 数组中数字出现的次数
    一个整型数组nums里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。示例1:输入:nums=[4,1,4,6]输出:[1,6]或[6,1]示例2:输入:nums=[1,2,10,4,1,4,3,3]输出:[2,10]或[10,2]限制:2<=nums.length......
  • 用 Go 剑指 Offer 31. 栈的压入、弹出序列 (辅助栈)
    输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如,序列{1,2,3,4,5}是某栈的压栈序列,序列{4,5,3,2,1}是该压栈序列对应的一个弹出序列,但{4,3,5,1,2}就不可能是该压栈序列的弹出序列。示例1:输入:pushe......
  • (动态规划)剑指 Offer 14- II. 剪绳子 II
    题目描述:给你一根长度为n的绳子,请把绳子剪成整数长度的m 段(m、n都是整数,n>1并且m>1),每段绳子的长度记为k[0],k[1]...k[m-1]。请问k[0]*k[1]*...*k[m-1]可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。答案......
  • 动态规划:剑指 Offer 14- I. 剪绳子
    题目描述:给你一根长度为n的绳子,请把绳子剪成整数长度的m段(m、n都是整数,n>1并且m>1),每段绳子的长度记为k[0],k[1]...k[m-1]。请问k[0]*k[1]*...*k[m-1]可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。  提......
  • 亿方云:2019年云综合收入0.60亿元,360的好帮手
     云排名分析:亿方云,2019年云综合收入0.60亿元。 2020年4月,360公司公告全资收购企业文件管理与协作SaaS服务商亿方云,即杭州亿方云网络科技有限公司。只是收购完成后,亿方云将保持独立发展。当然,进入360集团的旗下,可以获得更多资源的互补,特别是与360安全云盘形成互补与配合发展。对......