当前位置:网站首页>【剑指 Offer】 60. n个骰子的点数
【剑指 Offer】 60. n个骰子的点数
2022-07-06 10:11:00 【LuZhouShiLi】
剑指 Offer 60. n个骰子的点数
题目
把n个骰子扔在地上,所有骰子朝上一面的点数之和为s。输入n,打印出s的所有可能的值出现的概率。你需要用一个浮点数数组返回答案,其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
思路
- 首先用数组的第一维表示阶段,也就是投掷完几个骰子
- 然后用数组的第二维表示投掷完这些骰子之后,可能出现的点数
- 数组的值就表示,该阶段各个点数出现的次数
代码
class Solution {
public:
vector<double> dicesProbability(int n) {
int dp[12][70];
memset(dp,0,sizeof(dp));// 全部初始化0
for(int i = 1; i <= 6; i++)
{
dp[1][i] = 1;// 状态数组初始化
}
for(int i = 2; i <= n; i++)
{
// 最大点数 一定是 6 * i
for(int j = i; j <= 6 * i; j++)
{
for(int cur = 1; cur <= 6; cur++)
{
if(j - cur <= 0)
{
break;
}
// 但看第i个骰子,点数可能为1 2 3 4 5 6 因此点数j出现的次数是由投掷完第 i - 1个骰子 对应点数 j - 1 j - 2 j - 6 出现的次数之和转化过来的
dp[i][j] += dp[i - 1][j - cur];
}
}
}
int all = pow(6,n);// 所有可能性
vector<double> ret;
for(int i = n; i <= n * 6; i++)
{
ret.push_back(dp[n][i] * 1.0 / all);
}
return ret;
}
};
边栏推荐
- SAP UI5 框架的 manifest.json
- The integrated real-time HTAP database stonedb, how to replace MySQL and achieve nearly a hundredfold performance improvement
- MS-TCT:Inria&SBU提出用于动作检测的多尺度时间Transformer,效果SOTA!已开源!(CVPR2022)...
- Declval (example of return value of guidance function)
- 30 分钟看懂 PCA 主成分分析
- Jielizhi obtains the currently used dial information [chapter]
- 基本磁盘与动态磁盘 RAID磁盘冗余阵列区分
- Awk command exercise
- 【Android】Kotlin代码编写规范化文档
- 8位MCU跑RTOS有没有意义?
猜你喜欢
node の SQLite
面试突击62:group by 有哪些注意事项?
C语言指针*p++、*(p++)、*++p、*(++p)、(*p)++、++(*p)对比实例
IP, subnet mask, gateway, default gateway
【Android】Kotlin代码编写规范化文档
[introduction to MySQL] the first sentence · first time in the "database" Mainland
1700C - Helping the Nature
How to solve the error "press any to exit" when deploying multiple easycvr on one server?
Awk command exercise
node の SQLite
随机推荐
What is the reason why the video cannot be played normally after the easycvr access device turns on the audio?
Alibaba brand data bank: introduction to the most complete data bank
d绑定函数
微信为什么使用 SQLite 保存聊天记录?
This article discusses the memory layout of objects in the JVM, as well as the principle and application of memory alignment and compression pointer
一体化实时 HTAP 数据库 StoneDB,如何替换 MySQL 并实现近百倍性能提升
Interview assault 63: how to remove duplication in MySQL?
Appium automated test scroll and drag_ and_ Drop slides according to element position
Awk command exercise
OliveTin能在网页上安全运行shell命令(上)
Transfer data to event object in wechat applet
从交互模型中蒸馏知识!中科大&美团提出VIRT,兼具双塔模型的效率和交互模型的性能,在文本匹配上实现性能和效率的平衡!...
传输层 拥塞控制-慢开始和拥塞避免 快重传 快恢复
模板于泛型编程之declval
Interview shock 62: what are the precautions for group by?
OpenEuler 会长久吗
The difference between parallelism and concurrency
递归的方式
Smart street lamp based on stm32+ Huawei cloud IOT design
微信小程序中给event对象传递数据