New 21 game

LeetCode 837 New 21 Game

Medium

Alice plays the following game, loosely based on the card game “21”.

Alice starts with 0 points, and draws numbers while she has less than K points. During each draw, she gains an integer number of points randomly from the range [1, W], where W is an integer. Each draw is independent and the outcomes have equal probabilities.

Alice stops drawing numbers when she gets K or more points. What is the probability that she has N or less points?

大意：从1到W中随机选取数字，但是当分数达到或者超过K就停止，问最后总分小等于N的概率？

这个问题看上去就像一个DP问题。但是因为有了概率看起来就没那么好解决。但其实问概率还是在求和， 最终其实是小于N的完结状态比上所有完结状态。

解决DP问题，就要先要找到状态转移的方式。这里姑且可以看做，已知到达之前一点的概率，求到现在这个点的概率。最后的概率就是到所有完结点（K到N中间的N-K+1)个点的概率的和(到达这些点的概率是相互独立的)。

转移方式确定了之后就要找基础情况。

易知：f(0) = 1(必然到达）, f(1) = 1/w， f(2) = 1/w * f(0) + 1/w * f(1), f(3) = 1/w + 1/w * f(2) + 1/w * f(1)…

(从每个点过来的概率都是1/w)

在1-W之间（暂不考虑N特别小的情况），到达每一个点的概率为

f(i) = 1/w * sum(f(0 … i - 1))

当到达w + 1的时候，因为最大的步长是w所以这个时候我们是不能从0到达的，所以

f(w + 1) = 1 / w * (sum(f(0 … w)) - f(0))

同理，

f(w + 2) = 1 / w * (sum(f(0 … w + 1)) - f(1) - f(0))

这样，我们发现我们其实可以维护一个区间和，当这个区间在向前移动的时候加上新增的值，同时减掉已经出去的值。

对于0到k-1之间的概率显然都可以这么处理。对于最后的终结条件，其实也差不多，只是区间移动的时候不再新增值（因为是终止条件）。这种做法需要保证N < K + W

对于两种特例, K 为 0的时候，或者N >= K + W的时候，直接返回1即可。（在这种统计方法下会得到不正确的终结节点结果）

其实还有一个特例，就是当N为0 的时候，可以直接返回0，但是其实可以免除，因为最后终结点统计的时候for循环不会运行，自然是0。

class Solution {
public:
    double new21Game(int N, int K, int W) {
        if (K == 0 || N >= K + W) return 1.0;
        double total = 1, result = 0;
        vector<int> f(W, 0);
        f[W - 1] = 1;
        for (int i = 0; i < k; i++) {
            int prob = total / W;
            f.push_back(prob);
            total += prob;
            total -= f[0];
            f.pop_fonrt();
        }
        for (int i = 0; i <= N - K; i++) {
            result += total / W;
            if (f.size() > 0) {
                total -= f[0];
                f.pop_front();
            }
        }
        return result;
    }
};