LeetCode837.新21点

电玩女神 2023-02-14 13:27 13阅读 0赞

## 问题描述： ##

爱丽丝参与一个大致基于纸牌游戏 “21点” 规则的游戏，描述如下：

爱丽丝以 0 分开始，并在她的得分少于 K 分时抽取数字。 抽取时，她从 \[1, W\] 的范围中随机获得一个整数作为分数进行累计，其中 W 是整数。 每次抽取都是独立的，其结果具有相同的概率。

当爱丽丝获得不少于 K 分时，她就停止抽取数字。 爱丽丝的分数不超过 N 的概率是多少？

来源：力扣（LeetCode）  
链接：[https://leetcode-cn.com/problems/new-21-game][https_leetcode-cn.com_problems_new-21-game]

示例 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

## 解题思路： ##

以 n=21,k=17,w=3为例讲解：  
dp\[i\]表示的是当总共分数为i时的概率为dp\[i\],

所以最终的解是dp\[17\]+dp\[18\]+dp\[19\]+dp\[20\]+dp\[21\],那么dp\[21\]可以如何求得呢  
dp\[21\]可能是18+3，19+2，20+1转移求得的，

所以dp\[21\]的概率为之前去的18，19，20概率之和乘上1/w(1/w表示的是w个数取得其中一个)，

公式就是![\\small dp\[21\]=dp\[20\]\*1/w+dp\[19\]\*1/w+dp\[18\]\*1/w=1/w(dp\[18\]+dp\[19\]+dp\[20\])][small dp_21_dp_20_1_w_dp_19_1_w_dp_18_1_w_1_w_dp_18_dp_19_dp_20]

完整代码如下：

class Solution {
    public:
        double new21Game(int N, int K, int W) {
            if(K==0) return 1.0;
            if(N==0 || K>N) return 0;
            vector<double> dp(N+1,0.0);
            double sum = 1.0;
            double res = 0.0;
            dp[0] = 1.0;
            for(int i=1;i<=N;i++){
                dp[i] = 1.0*sum/W;
                if(i<K) sum+=dp[i];
                else res+=dp[i];//符合要求 K<=i<=N
                if(i>=W) sum-=dp[i-W];//sum只能容纳W个
            }
            return res;
        }
    };

[https_leetcode-cn.com_problems_new-21-game]: https://leetcode-cn.com/problems/new-21-game
[small dp_21_dp_20_1_w_dp_19_1_w_dp_18_1_w_1_w_dp_18_dp_19_dp_20]: https://private.codecogs.com/gif.latex?%5Csmall%20dp%5B21%5D%3Ddp%5B20%5D*1/w&plus;dp%5B19%5D*1/w&plus;dp%5B18%5D*1/w%3D1/w%28dp%5B18%5D&plus;dp%5B19%5D&plus;dp%5B20%5D%29