力扣——837. 新 21 点（Java实现DP）

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

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

当爱丽丝获得 k 分 或更多分 时，她就停止抽取数字。

爱丽丝的分数不超过 n 的概率是多少？

与实际答案误差不超过 10-5 的答案将被视为正确答案。

示例 1：

输入：n = 10, k = 1, maxPts = 10
输出：1.00000
解释：爱丽丝得到一张牌，然后停止。
示例 2：

输入：n = 6, k = 1, maxPts = 10
输出：0.60000
解释：爱丽丝得到一张牌，然后停止。 在 10 种可能性中的 6 种情况下，她的得分不超过 6 分。
示例 3：

输入：n = 21, k = 17, maxPts = 10
输出：0.73278

代码1：

class Solution {
    public double new21Game(int N, int K, int W) {
        // 先判断 K - 1 + W 是否在 N 的里面，如果在的话，说明肯定能赢得游戏，返回 1.0，也就是 100%
        if (N - K + 1 >= W) {
            return 1.0;
        }
        double[] dp = new double[K + W];
        // 将能赢得游戏的点数的概率设置为 1
        for (int i = K; i <= N; i++) {
            dp[i] = 1.0;
        }
        // 计算K + W 这几个点数的概率和
        double sumProb = N - K + 1;
        // 从 K - 1 开始计算，
        for (int i = K - 1; i >= 0; i--) {
            // 点数为 i 的赢得游戏的概率为 i + 1 ~ i + W 的概率和除以 W 
            dp[i] = sumProb / W;
            sumProb = sumProb - dp[i + W] + dp[i];
        }

        return dp[0];
    }
}

代码2：

class Solution {
      public double new21Game(int N, int K, int W) {
        double res = 0;

        int bound = (N<K+W)?N:K+W;
        double dp[] = new double[bound+1];
        double p = (double) 1 / W;
        dp[0] = 1;
        
        
        int lower = 0;
        double acc = 0;
        for(int i = 1; i <= bound; i++){            
            if(lower < i-W){
                acc -= dp[lower];
                lower++;                
            }
            if(i<=K){               
                acc += dp[i-1];
            }
            dp[i] = acc * p;
        }
        for(int q = K; q <= bound; q++){
            res += dp[q];
        }
        return res;
    }
 
}

作者：KJ.JK
本文仅用于交流学习，未经作者允许，禁止转载，更勿做其他用途，违者必究。
文章对你有所帮助的话，欢迎给个赞或者 star，你的支持是对作者最大的鼓励，不足之处可以在评论区多多指正，交流学习