[leetcode] 837. New 21 Game

[leetcode] 837. New 21 Game

Description

Alice plays the following game, loosely based on the card game “21”.

Alice starts with 0 points, and draws numbers while she has less than K points. During each draw, she gains an integer number of points randomly from the range [1, W], where W is an integer. Each draw is independent and the outcomes have equal probabilities.

Alice stops drawing numbers when she gets K or more points. What is the probability that she has N or less points?

Example 1:

Input: N = 10, K = 1, W = 10Output: 1.00000Explanation: Alice gets a single card, then stops.

Example 2:

Input: N = 6, K = 1, W = 10Output: 0.60000Explanation: Alice gets a single card, then stops.In 6 out of W = 10 possibilities, she is at or below N = 6 points.

Example 3:

Input: N = 21, K = 17, W = 10Output: 0.73278

Note:

0 <= K <= N <= 100001 <= W <= 10000Answers will be accepted as correct if they are within 10^-5 of the correct answer.The judging time limit has been reduced for this question.

分析

题目的意思是：一个人从0开始摸数字，这个人只有k个点，每次会得到一个数，这个数会随机的从[1,W]里面产生，问我们当拿到不少于K点的时候就停止画数字，最终点数能不超过的N点的概率。

这个必须动态规划，其他方法做起来有点麻烦，并且这个题目我在笔试的时候遇见了几次，所以弄懂是很有意义的。dp[i]: 为得到点数i的概率dp[i] = sum(last W dp values) / W 维护一个至多为K的滑动窗口就行了例如：

N为10，K为1，W为10的情况，由于如果拿到的数不少于K就不能拿牌了，这个例子中不少于1就行了，因此[1,10]中不管拿哪个都不小于1，并且点数也没有超过N,所以概率为1.N = 6, K = 1, W = 10的情况，由于如果拿到的数不少于K就不能拿牌了，这个例子中不少于1就行了，因此[1,10]中不管拿哪个都不小于1，另外N为6，所以不和不超过6的情况有[1,6]这6种情况，最终是6/10=0.6N = 21, K = 17, W = 10的情况，由于如果拿到的数不少于K就不能拿牌了，这个例子中不少于17，因此第一次摸牌的区间为[1,10]，还是小于17，因此要继续莫，第二次摸牌的区间还是[1,10]，其中7+10，8+9，8+10，9+8，9+9，9+10，10+7，10+8，10+9，10+10的组合会停止摸牌，如果第一次摸的牌小于等于6，则要进行至少三轮，如果大于6，则还要分情况讨论。弄清这种关系还是比较麻烦，因此需要进行分析了。 每次摸牌的点数都是从[1,10]中取，因此摸牌之间是相互独立的。但是最终结果会与前一次的结果相关，环环相扣，这个很显然要用动态规划。

利用贝叶斯公式： 在不小于K点的前提下，还能不超过N点的概率，等于拿到不小于K点且不超过N点的概率除以拿到不小于K点的概率。P(x<=N && x>=K) 和 P(x>=K) p=P(x>=K&&x<=N)/P(x>=K) P(x>=K&&x<=N)=P(x=K)+P(x=K+1)+…+P(x=N) P(x>=K)=P(x=K)+P(x=K+1)+…+P(x=N)+…+P(x=K+W-1) 因此，分类讨论：

当K=0时，由于题目中说当前点数大于等于K，不能摸牌，那么一开始就不能摸牌了，而 K <= N，所以永远不会超过N，概率返回1。当 N >= K+W 的时候，当我们大于等于K的时候，不能摸牌，此时不会超过N。 当刚好为K-1的时候，此时还有一次摸牌机会，但最大也就摸个W，总共为K-1+W，还是小于N，所以返回概率为1。对于 i <= W 的情况下：比如上面的例3. 求7点的概率为：P[7] = 1/W * (P[6] + p[5] + … + P[1] + P[0]) = 1/W * sum[6]P[i] = 1/W * sum[i-1] ，其中，sum[i] = sum[i-1] + P[i] = sum[i-1] + sum[i-1] / W (当 i <= W)当i>W的时候，比如求15点的概率：P[15] = 1/W * (P[14] + P[13] + … + P[5]) = 1/W * (sum[14] - sum[4])P[i] = 1/W * (sum[i-1] - sum[i-W-1])sum[i] = sum[i-1] + P[i] = sum[i-1] + (sum[i-1] - sum[i-W-1]) / W (当 i > W)考虑W的情况就是：比如当K=17时，我们要更新P[15]P[i] = 1/W * sum[i-1] (when i <= K && i <= W)P[i] = 1/W * (sum[i-1] - sum[i-W-1]) (当 i <= K && i > W)考虑到i大于K的情况，比如为20点的时候P[20] = 1/W * (P[16] + P[15] + P[14] + … + P[10]) = 1/W * (sum[16] - sum[9])P[i] = 1/W * sum[K-1] (when i > K && i <= W)P[i] = 1/W * (sum[K-1] - sum[i-W-1]) (当 i > K && i > W)所以结果就出来了，转换成代码就行了。

代码

class Solution {public: double new21Game(int N, int K, int W) { if(K==0||N>=K+W){ return 1.0; } vector dp(N+1,0); dp[0]=1.0; double Wsum=1.0; double res=0; for(int i=1;i<=N;i++){ dp[i]=Wsum/W; if(i=0){ Wsum-=dp[i-W]; } } return res; }};

参考文献

​​837. New 21 Game​​​​[LeetCode] New 21 Game 新二十一点游戏​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。