做男鞋的网站,wap网站和internet网站,网站幻灯片效果代码,海南省建设集团有限公司网站文章目录1. 题目2. 解题2.1 暴力超时2.2 优化1. 题目
爱丽丝参与一个大致基于纸牌游戏 “21点” 规则的游戏#xff0c;描述如下#xff1a;
爱丽丝以 0 分开始#xff0c;并在她的得分少于 K 分时抽取数字。 抽取时#xff0c;她从 [1, W] 的范围中随机获得一个整数作为…
文章目录1. 题目2. 解题2.1 暴力超时2.2 优化1. 题目
爱丽丝参与一个大致基于纸牌游戏 “21点” 规则的游戏描述如下
爱丽丝以 0 分开始并在她的得分少于 K 分时抽取数字。 抽取时她从 [1, W] 的范围中随机获得一个整数作为分数进行累计其中 W 是整数。 每次抽取都是独立的其结果具有相同的概率。
当爱丽丝获得 K 分时她就停止抽取数字。 爱丽丝的分数不超过 N 的概率是多少
示例 1
输入N 10, K 1, W 10
输出1.00000
说明爱丽丝得到一张卡然后停止。示例 2
输入N 6, K 1, W 10
输出0.60000
说明爱丽丝得到一张卡然后停止。
在 W 10 的 6 种可能下她的得分不超过 N 6 分。示例 3
输入N 21, K 17, W 10
输出0.73278提示
0 K N 10000
1 W 10000
如果答案与正确答案的误差不超过 10^-5则该答案将被视为正确答案通过。
此问题的判断限制时间已经减少。来源力扣LeetCode 链接https://leetcode-cn.com/problems/new-21-game 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
2.1 暴力超时
每个位置等于它前面w个位置以 1/w的该跳过来的概率值和105 / 146 个通过测试用例
9811 # 超时
8890
7719class Solution {
public:double new21Game(int N, int K, int W) {vectordouble dp(N1, 0.0);dp[0] 1.0;int i, wi;for(i 0; i K; i){for(wi 1; wi W; wi){if(iwi N)dp[iwi] dp[i]/W;}}double ans 0.0;for(i K; i N; i)ans dp[i];return ans;}
};2.2 优化
每个位置 i 之前的W个位置相当于滑动窗口的概率之和prob到达 i 的的概率为 prob/W
class Solution {
public:double new21Game(int N, int K, int W) {vectordouble dp(N1, 0.0);if(K 0 || N K W) return 1.0;//肯定不会超出Ndp[0] 1;double prob 1.0;//停在 i前面 w个位置的概率之和 初值在0位置概率为1int i;for(i 1; i K; i)//小于K时可以继续w个前缀可以加上本次的概率{if(i W){dp[i] prob/W;//前面所有的位置都可以到此处每个位置乘以1/wprob dp[i];//前缀概率和本次}else //超过w个了{dp[i] (prob-dp[i-W-1])/W;//不在窗口内的不能到i处了需要减去prob dp[i] - dp[i-W-1];//前缀本次-不在窗口内的}}for( ; i K i N; i)// K 了 不能再走了不加本次的概率{if(i W)dp[i] prob/W;else{dp[i] (prob-dp[i-W-1])/W;prob - dp[i-W-1];//不加本次的概率在窗口w外的减去}}for(i K, prob 0.0; i N; i)prob dp[i];return prob;}
};4 ms 9.4 MB
