LeetCode.837.New 21 Game 新21点

题目描述

837 New 21 Game
https://leetcode-cn.com/problems/new-21-game/

爱丽丝参与一个大致基于纸牌游戏 “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，则该答案将被视为正确答案通过。
此问题的判断限制时间已经减少。

---

解题过程

获胜的概率只和下一次抽牌开始前手中累积的点数有关
设 dp[i] 表示手中累积的点数是 i 时继续游戏直到结束的胜率，即停止抽牌后点数小于等于 n 的概率。
则 i 的取值可以从 0 到 k-1+w，因为可抽牌的手中最大点数是 k-1，抽到的最大牌面是 w，所以手中的点数最大是 k-1+w，所以 dp 数组的长度需要是 k+w，dp[0] 就是所求的最终结果。

我们可以从后往前填表
i >= k 时，当前累积点数大于等于 k 时无法再抽牌，直接根据手中的点数可计算胜率，小于等于 n 则胜率为1，大于 n 则胜率为 0
i < k 时，当前累积点数小于 k 时可继续抽牌，抽到的牌面可能是 1 到 w 中任意一张，概率都是 1/w，所以胜率是后面 w 种可能的概率的平均值，则有递推公式 dp[i] = (dp[i+1] + dp[i+2] + ... + dp[i+w]) / w, i < k

可以看到当计算 i < k 的 dp[i] 值时，我们需要其后面 w 个元素的和，如果每次都 O(w) 往后累加计算一次，总的时间复杂度会变为 O(kw)
可以利用 前缀和 的思想，空间换时间，从后往前计算时保存后缀和，则每次直接通过差分就能得到后续 w 个元素的和。

其实还可以利用 滚动数组 进一步对空间复杂度进行优化，我们用一个变量 suffixSum 保存当前元素后 w 个元素的和，每次计算后更新 suffixSum 的值，加上当前结果 dp[i] 并减去第 w 个元素 dp[i+w]，即 suffixSum += dp[i] - dp[i+w]，可将空间复杂度降到 O(1)

时间复杂度 O(n)，下面的代码没对空间进行优化，空间复杂度还是 O(n)

private static class SolutionV202006 {
    public double new21Game(int n, int k, int w) {
        // dp[i] 表示手里累积的点数是 i 时继续游戏直到结束的胜率（即停止抽牌后点数小于等于n的概率）
        double[] dp = new double[k + w];
        // dp 数组的后缀和数组，长度比原数组多1，方便直接累加最后一个元素
        double[] suffixSum = new double[k + w + 1];

        for (int i = dp.length - 1; i >= 0; i--) {
            if (i >= k) {
                // 当前累积点数大于等于 k 时无法再抽牌，直接根据手中的点数可计算胜率，小于等于 n 则胜率为1，大于 n 则胜率为 0
                dp[i] = (i <= n ? 1 : 0);
            } else {
                // 当前累积点数小于 k 时可继续抽牌，抽到的牌面可能是 1 到 w 中任意一张，概率都是 1/w，所以胜率是后面 w 种可能的概率的平均值
                dp[i] = (suffixSum[i+1] - suffixSum[i + w + 1]) / w;
            }
            suffixSum[i] = suffixSum[i+1] + dp[i];
        }
        return dp[0];
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_837_New21Game.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_837_New21Game.java

---