当前位置: 首页 > news >正文

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

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

难度:middle\color{orange}{middle}middle


题目描述

把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]复制示例输入

限制:

1<=n<=111 <= n <= 111<=n<=11


算法

(动态规划)

设输入 n 个骰子的解(即概率列表)为 f(n) ,其中「点数和」 x 的概率为 f(n,x)

假设已知 n−1 个骰子的解 f(n−1) ,此时添加一枚骰子,求 n 个骰子的点数和为 x 的概率 f(n,x) 。

当添加骰子的点数为 1 时,前 n−1 个骰子的点数和应为 x−1 ,方可组成点数和 x ;同理,当此骰子为 2 时,前 n−1 个骰子应为 x−2 ;以此类推,直至此骰子点数为 6 。将这 6 种情况的概率相加,即可得到概率 f(n,x) 。递推公式如下所示:

f(n,x)=∑i=16f(n−1,x−i)∗1/6f(n, x) = \sum_{i=1}^6f(n - 1, x - i) * 1 / 6f(n,x)=i=16f(n1,xi)1/6

复杂度分析

  • 时间复杂度O(n2)O(n^2)O(n2)

  • 空间复杂度 : O(n)O(n)O(n)

C++ 代码

class Solution {
public:vector<double> dicesProbability(int n) {vector<double> res(n * 5 + 1);vector<vector<double>> f(n + 1, vector<double>(n * 6 + 1, 0));for (int i = 1; i <= 6; i ++)f[1][i] = 1.0 / 6;for (int i = 2; i <= n; i ++)for (int j = i; j <= i * 6; j ++)for (int k = 1; k <= 6; k ++){if (j - k >= i - 1)f[i][j] += f[i - 1][j - k]/6;}for (int i = 0; i <= n * 5; i ++)res[i] = f[n][n + i];return res;}
};

相关文章:

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

剑指 Offer 60. n个骰子的点数 难度&#xff1a;middle\color{orange}{middle}middle 题目描述 把n个骰子扔在地上&#xff0c;所有骰子朝上一面的点数之和为s。输入n&#xff0c;打印出s的所有可能的值出现的概率。 你需要用一个浮点数数组返回答案&#xff0c;其中第 i 个…...

阿里巴巴-淘宝搜索排序算法学习

模型效能&#xff1a;模型结构优化 模型效能&#xff1a;减枝 FLOPS&#xff1a;每秒浮点运算的次数 模型效能&#xff1a;量化 基于统计阈值限定&#xff0c;基于学习阈值限定。 平台效能&#xff1a;一站式DL训练平台 平台效能&#xff1a;搜索模型的系统流程 协同关系…...

〖Python网络爬虫实战⑮〗- pyquery的使用

订阅&#xff1a;新手可以订阅我的其他专栏。免费阶段订阅量1000python项目实战 Python编程基础教程系列&#xff08;零基础小白搬砖逆袭) 说明&#xff1a;本专栏持续更新中&#xff0c;目前专栏免费订阅&#xff0c;在转为付费专栏前订阅本专栏的&#xff0c;可以免费订阅付费…...

SQL综合查询下

SQL综合查询下 目录SQL综合查询下18、查询所有人都选修了的课程号与课程名题目代码题解19、SQL查询&#xff1a;查询没有参加选课的学生。题目代码20、SQL查询&#xff1a;统计各门课程选修人数&#xff0c;要求输出课程代号&#xff0c;课程名&#xff0c;有成绩人数&#xff…...

全连接层FC

lenet结构: 输入层(Input Layer):接收手写数字的图像数据,通常是28x28的灰度图像。 卷积层1(Convolutional Layer 1):对输入图像进行卷积操作,提取低级别的特征,使用 6 个大小为 5x5 的卷积核进行卷积,得到 6 个输出特征图,激活函数为 Sigmoid。 平均池化层1(Aver…...

图的遍历及连通性

文章目录 图的遍历及连通性程序设计程序分析图的遍历及连通性 【问题描述】 根据输入的图的邻接矩阵A,判断此图的连通分量的个数。 【输入形式】 第一行为图的结点个数n,之后的n行为邻接矩阵的内容,每行n个数表示。其中A[i][j]=1表示两个结点邻接,而A[i][j]=0表示两个结点无…...

DJ3-4 实时调度

目录 3.4.1 实现实时调度的基本条件 1. 提供必要的信息 2. 系统的处理能力强 3. 采用抢占式调度机制 4. 具有快速切换机制 3.4.2 实时调度算法的分类 1. 非抢占式调度算法 2. 抢占式调度算法 3.4.3 常用的几种实时调度算法 1. 最早截止时间优先 EDF&#xff08;Ea…...

Oracle之PL/SQL游标练习题(三)

游标练习题目1、定义游标&#xff1a;列出每个员工的姓名部门名称并编程显示第10个到第20个记录2、定义游标&#xff1a;从雇员表中显示工资大于3000的记录&#xff0c;只要姓名、部门编号和工资&#xff0c;编程显示其中的奇数记录3、用游标显示所有部门编号与名称&#xff0c…...

docker运行服务端性能监控系统Prometheus和数据分析系统Grafana

文章目录一、Prometheus的安装和运行1、使用docker拉取镜像2、创建prometheus.yml文件3、启动容器4、查看启动是否成功5、记录安装过程中出现的错误二、Grafana的安装和运行1、使用docker拉取镜像2、创建grafana3、运行grafana4、查看grafana运行日志5、登录grafana一、Prometh…...

【Linux】【应用层】多线程编程

一、线程创建 Linux 中的 pthread_create() 函数用来创建线程&#xff0c;它声明在<pthread.h>头文件中&#xff0c;语法格式如下&#xff1a; int pthread_create(pthread_t *thread,const pthread_attr_t *attr,void *(*start_routine) (void *),void *arg);各个参数…...

GameFramework 框架详解之 如何接入热更框架HybridCLR

一.前言 HybridCLR是一个特性完整、零成本、高性能、低内存的近乎完美的c#热更新方案 GameFramework是一个非常出色完整的基于Unity引擎的游戏框架,里面包含了非常多的模块,封装非常完整。 以前市面上的热更大多数都是Lua为主,后来出了一个ILRuntime的C#热更框架,虽然性能…...

全国青少年软件编程(Scratch)等级考试二级考试真题2023年3月——持续更新.....

一、单选题(共25题,共50分) 1. 小猫的程序如图所示,积木块的颜色与球的颜色一致。点击绿旗执行程序后,下列说法正确的是?( ) A.小猫一直在左右移动,嘴里一直说着“抓到了”。 B.小猫会碰到球,然后停止。 C.小猫一直在左右移动,嘴里一直说着“别跑” D.小猫会碰到球,…...

HTML2.1列表标签

列表标签种类 无序列表 有序列表 自定义列表 使用场景&#xff1a;在列表中按照行展示关联性内容。 特点&#xff1a;按照行的形式&#xff0c;整齐显示内容。 一、无序列表 标签名说明ul无序列表整体&#xff0c;用于包裹li标签li表示无序列表的每一项&#xff0c;用于包…...

在 Flutter 多人视频通话中实现虚拟背景、美颜与空间音效

前言 在之前的「基于声网 Flutter SDK 实现多人视频通话」里&#xff0c;我们通过 Flutter 声网 SDK 完美实现了跨平台和多人视频通话的效果&#xff0c;那么本篇我们将在之前例子的基础上进阶介绍一些常用的特效功能&#xff0c;包括虚拟背景、色彩增强、空间音频、基础变声…...

Ambari-web 架构

Ambari-web 使用的前端 Embar.js MVC 框架实现&#xff0c;Embar.js 是一个 TodoMVC 框架&#xff0c;涵盖了单页面应用&#xff08;single page application&#xff09;几乎所有的行为 Nodejs 是一个基于 Chrome JavaScript 运行时建立的一个平台&#xff0c;用来方便的搭建…...

对接百思买Best Buy EDI 的注意事项

在此前的文章&#xff1a;《Best Buy Drop Ship(Commerce hub) EDI业务测试常见报错及解决》中&#xff0c;我们介绍了在业务测试过程中遇到的常见报错及解决方案&#xff0c;以下在此基础上进行补充。 数据未能成功发送给Best Buy可能遇到的情况 Best Buy EDI项目传输业务报…...

2023年郑州重点建设项目名单公布,中创“算力数据中心”项目入选!

4月7日&#xff0c;郑州市人民政府网站公布2023年郑州市重点建设项目名单&#xff0c;名单共列项目680个&#xff0c;总投资1.08万亿元&#xff0c;年度计划投资2691亿元。 在创新驱动能力提升项目名单里&#xff0c;中创算力与人民网人民数据&#xff08;国家大数据灾备中心&a…...

Pytorch 容器 - 1. Module类介绍

目录 1. 基于Module构建自己的网络 2. Module的初始化变量 3. Modules中需要子类 forward() 4. Modules中其他内置函数 1. 基于Module构建自己的网络 torch.nn.Module是所有神经网络模块的基类&#xff0c;如何定义自已的网络&#xff1a; 由于 Module 是神经网络模块的基…...

百度墨卡托坐标转化笔记

一、墨卡托坐标转化 调研了python和java多种实现方式的转换&#xff0c;发现有的不符合需求&#xff0c;原因还没找到。 我是用百度地图返回的poi边界&#xff08;返回的是墨卡托坐标&#xff09; 转换的原理没有深入研究&#xff0c;直接拿来用的&#xff0c;测试可行&…...

每日学术速递4.12

CV - 计算机视觉 | ML - 机器学习 | RL - 强化学习 | NLP 自然语言处理 Subjects: cs.HC 随着新的“生成代理”论文的发布&#xff0c;LLM刚刚达到了一个重要的里程碑——通过使用 LLM&#xff0c;生成代理能够在受《模拟人生》启发的交互式沙箱中模拟类人行为。代理架构扩展…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序

一、开发准备 ​​环境搭建​​&#xff1a; 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 ​​项目创建​​&#xff1a; File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...

ArcGIS Pro制作水平横向图例+多级标注

今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作&#xff1a;ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等&#xff08;ArcGIS出图图例8大技巧&#xff09;&#xff0c;那这次我们看看ArcGIS Pro如何更加快捷的操作。…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...