今天这题真的。。。不单单只是DP呀，真的像评论区朋友说的，没加数学标签真的是屈才了。面试碰到果断回家等消息。

题目

837.爱丽丝参与一个大致基于纸牌游戏 “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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

做这道题前，强烈建议概率论已经积灰的童鞋先去看一看，不然还真不是很好理解动态转移方程，自己推导也是有一定难度的。
我们可以认为游戏停止时，爱丽丝手中的分数不大于N为胜利，反之为失败。
记动态规划数组为dp，dp[i]表示当前手中的分数为i的情况下，获胜的概率，i的取值范围为0-K-1+W，目标是求得dp[0]。根据题目对于K，W的定义，每一次我们的抽牌活动，获得1-W的分数的概率相同，均为1/W，由于分数大于等于K时就会停止，即停止前，手中最大的分数为K-1。接下来，进行一次抽牌，分数必然超过K，最大为K-1+W。试想，此时的获胜概率是多少呢？显然，K<=i<=min(N,K-1+W)时，dp[i]=1，反之为0。
再来看当i<K时。记手中分数等于i时获胜为事件B，接下去筹牌结果为事件A1、A2……Aw，即P(A1)=P(A2)=……=P(Aw)=1/W。由于A1、A2……Aw相互独立，它们构成全集，根据全概率公式，
P(B)=P(A1B)+P(A2B)+……+P(AwB)
=P(A1)*P(B|A1)+……+P(Aw)*P(B|Aw)
=(P(B|A1)+……+P(B|Aw))/W。
得出DP方程：dp[x]= (dp[x+1]+dp[x+2]+⋯+dp[x+W])/W

代码

class Solution {
public:double new21Game(int N, int K, int W) {double res=1.0;if(K==0)return res;int score=0;vector<double> dp(K+W,0.0);for(int i=K;i<=N &&i<=K+W-1;i++)dp[i]=1;//此时i不小于K，停止游戏，且结果满足要求，概率必然为1double sum=0;for(int i=K;i<K+W;i++)sum+=dp[i];for(int i=K-1;i>=0;i--){dp[i]=sum/W;sum=sum+dp[i]-dp[i+W];}return dp[0];}
};