题目描述

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

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

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

样例

输入：N = 10, K = 1, W = 10
输出：1.00000
说明：爱丽丝得到一张卡，然后停止。

输入：N = 6, K = 1, W = 10
输出：0.60000
说明：爱丽丝得到一张卡，然后停止。
在 W = 10 的 6 种可能下，她的得分不超过 N = 6 分。

输入：N = 21, K = 17, W = 10
输出：0.73278

注意

• 0 <= K <= N <= 10000
• 1 <= W <= 10000
• 如果答案与正确答案的误差不超过 10^-5，则该答案将被视为正确答案通过。
• 此问题的判断限制时间已经减少。

算法

(动态规划) $O(n)$

1. 设 $f(i)$ 表示得到 $i$ 点分数的概率。
2. 初始时 $f(0) = 1$，其余为 $0$。
3. 转移时，枚举能从那些值得到 $i$，即 $j \in [i - W, i - 1]$ 且 $j >= 0, j < K$，$f(i) = f(i) + \frac{f(j)}{W}$。
4. 最终答案为 $f(K) + f(K + 1) + \dots + f(N)$。
5. 暴力枚举转移会超时，需要一个前缀和 $s(i)$ 来维护 $f(0) + f(1) + \dots + f(i)$ 的值，这样转移只需要 $O(1)$ 的时间。

时间复杂度

• 状态数 $n$ 个，转移只需要常数的的时间，故总时间复杂度为 $O(n)$。

空间复杂度

• 和状态数一致，故空间复杂度为 $O(n)$。

C++ 代码

class Solution {
public:
    double new21Game(int N, int K, int W) {
        if (K == 0) return 1.0;

        vector<double> f(N + 1, 0), s(N + 1, 0);
        f[0] = s[0] = 1;

        for (int i = 1; i <= N; i++) {
            int l = max(0, i - W), r = min(K - 1, i - 1);

            if (l <= r) {
                if (l == 0) f[i] = s[r] / W;
                else f[i] = (s[r] - s[l - 1]) / W;
            }

            s[i] = s[i - 1] + f[i];
        }

        return s[N] - s[K - 1];
    }
};