LeetCode837.新21分-蟒蛇

837。新21分题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/new-21-game题目爱丽丝参与了一场纸牌游戏，大致是根据“二十一点”的游戏规则，描述如下：爱丽丝从0分开始，当她的分数小于K分时抽号。绘画时，她通过从[1,W]范围内随机抽取一个整数来累积分数，其中W是一个整数。每次抽奖都是独立的，其结果的概率相同。当Alice得到不少于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<=100001<=W<=10000如果答案在正确答案的10^-5以内,答案将被接受为正确答案。减少了这道题的判断时限。解题思路：在动态规划问题中，提供了三个变量。N、K、W，这里简单解释一下这三个是什么？N：这相当于一个极限。题中要求的是最后抽取一个数，与N比较，决定输赢。K：表示有条件可以继续抽号。现在看例子1：N=10,K=1,W=10因为Alice是从0开始的，此时0min(N,K+W-1)$,dp[我]=0。那么现在我们求$0\leqifloat:dp=[0.0]*(K+W)#先处理概率为1.0的情况#是iFallsin[K,min(N,K+W-1)]Thispartforiinrange(K,min(N,K+W-1)+1):dp[i]=1.0#这里先计算K的情况-1#把导出的结果公式放在这里dp[K-1]=float(min(N-K+1,W)/W)#开始计算从K-2到dp[0]的值这里对于iinrange(K-2,-1,-1):dp[i]=dp[i+1]-(dp[i+W+1]-dp[i+1])/Wreturndp[0]实现结果总结题目中使用的思想是动态规划，这里的主要难点是状态转移方程的推导。根据题意，推导方向是从后面的情况往前面推导。先处理最后抽到的号码的情况，再依次类推。能否赢下比赛，关系到下一场平局前的比分。本次开奖的中奖概率实际上是后面开奖后累计分数是否超过N的概率之和。据此，可以得到状态转移方程。由于原始传递方程会超时，因此对其进行了优化。根据邻差，简化状态转移方程。如果您觉得文章写得不错，请点个关注。公众号《书所集录》同步更新，也欢迎大家关注。