LeetCode 837 - New 21 Game

https://leetcode.com/problems/new-21-game/description/

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?

Example 1:

Input: N = 10, K = 1, W = 10
Output: 1.00000
Explanation:  Alice gets a single card, then stops.

Example 2:

Input: N = 6, K = 1, W = 10
Output: 0.60000
Explanation:  Alice gets a single card, then stops.
In 6 out of W = 10 possibilities, she is at or below N = 6 points.

Example 3:

Input: N = 21, K = 17, W = 10
Output: 0.73278

Note:

1. 0 <= K <= N <= 10000
2. 1 <= W <= 10000
3. Answers will be accepted as correct if they are within 10^-5 of the correct answer.
4. The judging time limit has been reduced for this question.

http://www.programmersought.com/article/575237977/

Using dynamic programming, dp[i] represents the probability of getting the number of points i, and will continue to fetch only if the current total number of points is less than K. Then the state transition equation can be written as:

1. wheni <= KTime,Dp[i] = (the sum of the first W dp) / W; (climbing the stairs to get the probability that the total number of stairs is i)
2. whenK < i < K + WWhen, then the range of points in the previous time is[i - W, K - 1]. Our dp array represents the probability of getting the point i, sodp[i]=(dp[K-1]+dp[K-2]+…+dp[i-W])/W(You can select one of the [1, W] numbers from the previous basis)
3. When i>=K+W, this case should not exist anyway, so dp[i]=0.

https://leetcode.com/problems/new-21-game/discuss/228406/Logical-Thinking

point 0 initially
while (point < K) {
    draw w  from [1, W] randomly 
    point += w
}
probability(point <= N) ?

Let's observe that

point total range [0, K + W - 1]

we define probability[i] as probability to get i points
since all start with point 0 => probability[0] = 1

Probability transition:

Before we reach point `i`, we draw `w`, i.e., our last point is `i - w` 

probability to get i points = sum(probability to get i - w points * 1 / W) for w can be any of [1, W]
where 0 <= i - w < K

target probability = sum of prabability to get points [K, N]

Note

If K = 10, W = 10
draw 1, then 9, probability is P(1) * P(9) = 0.1 * 0.1 = 0.01
draw 10, probability is P(10) = 0.1.

(1, 9) and (10) can't be simply regarded as combination candidates for they don't share the same probability.

---

    public double new21Game(int N, int K, int W) {
        // Corner cases.
        if (K == 0) return 1;
        
        int maxPoint = K + W - 1;
        // probability[i] is probability of getting point i.
        double[] probability = new double[maxPoint + 1];
        
        probability[0] = 1;
        for (int i = 1; i <= maxPoint; i++) {
            for (int w = 1; w <= W; w++) {
                if (i - w >= 0 && i - w < K)
                    probability[i] += probability[i - w] * 1 / W;
            }
        }
        
        double targetProbability = 0; // Probability of N or less points.
        for (int i = K; i <= N; i++) {
            targetProbability += probability[i];
        }
        
        return targetProbability;
    }

https://leetcode.com/problems/new-21-game/discuss/132334/One-Pass-DP-O(N)

The same problems as "Climbing Stairs".

Explanation:
In a word,
dp[i]: probability of get points i
dp[i] = sum(last W dp values) / W

To get Wsum = sum(last W dp values), we can maintain a sliding window with size at most K.

    public double new21Game(int N, int K, int W) {
        if (K == 0 || N >= K + W) return 1;
        double dp[] = new double[N + 1],  Wsum = 1, res = 0;
        dp[0] = 1;
        for (int i = 1; i <= N; ++i) {
            dp[i] = Wsum / W;
            if (i < K) Wsum += dp[i]; else res += dp[i];
            if (i - W >= 0) Wsum -= dp[i - W];
        }
        return res;
    }

https://buptwc.com/2018/05/22/Leetcode-837-New-21-Game/
使用动态规划，dp[i]表示点数和为i的概率，那么最后结果应该是dp[k]+dp[k+1]+…+dp[n]
其中，dp[i]又应该为前w个的dp的平均值
例如W=10，那么dp[20] = 1/10 * (dp[10]+dp[11]+…+dp[19])

def new21Game(N, K, W):
    if K == 0: return 1
    dp = [1.0] + [0.0] * N
    # 用Wsum 记录前w个dp之和
    Wsum = 1.0000
    for i in range(1, N + 1):
        dp[i] = Wsum / W
        if i < K: Wsum += dp[i]
        # 假设K = 15，那么上面的例子d[20] = 1/10 * (dp[10]+...+dp[14]),因为拿到15之后就不能拿了，所以不存在从15拿5拿到20的情况
        if 0 <= i - W < K: Wsum -= dp[i - W]
    return sum(dp[K:])

https://www.acwing.com/solution/LeetCode/content/925/
设 f(i)f(i) 表示得到 ii 点分数的概率。
初始时 f(0)=1f(0)=1，其余为 00。转移时，枚举能从那些值得到 ii，即 j∈[i−W,i−1]j∈[i−W,i−1] 且 j>=0,j<Kj>=0,j<K，f(i)=f(i)+f(j)Wf(i)=f(i)+f(j)W。
最终答案为 f(K)+f(K+1)+⋯+f(N)f(K)+f(K+1)+⋯+f(N)。
如果暴力枚举转移会超时，需要一个前缀和 s(i)s(i) 来维护 f(0)+f(1)+⋯+f(i)f(0)+f(1)+⋯+f(i) 的值，这样转移只需要 O(1)O(1) 的时间。
时间复杂度
状态数 nn 个，优化转移只需要 O(1)O(1) 的时间，故总时间复杂度为 O(n)O(n)。


https://www.cnblogs.com/seyjs/p/9076034.html
这个题目有点像爬楼梯问题，只不过楼梯问题要求的计算多少种爬的方式，但是本题是计算概率。因为点数超过或者等于K后就不允许再增加新的点数了，因此我们可以确定最终Alice拥有的点数的区间是[K,K-1+W]，下限等于K很好理解，Alice最后一次抽取点数前可能拥有的点数最大值是K-1，最后一次抽取的点数最大值是W,因此上限就是K-1+W。和爬楼梯类似，恰好获得点数n的概率dp[n] = sum(dp[n-w]/w + dp[n-w+1]/w + .... dp[n-1]/w)。因为获取任意一个点数的概率都是1/W，所以上面的公式中每个dp都要除以W。但是题目约定了一个K值，在n > k + 1的情况下，dp[n]是无法通过dp[n-1]得到，需要修正公式： dp[n] = sum(dp[n-w]/w + dp[n-w+1]/w + .... dp[K-1]/w)。最后，点数小于或者等于N的概率就是 sum(dp[K:N + 1])

https://blog.csdn.net/fuxuemingzhu/article/details/83615241
类似爬楼梯的问题，每次可以跨[1,W]个楼梯，当一共爬了K个和以上的台阶时停止，问这个时候总台阶数<=N的概率。

使用动态规划，dp[i]表示得到点数i的概率，只有当现在的总点数少于K的时候，才会继续取数。那么状态转移方程可以写成：

当i <= K时，dp[i] = （前W个dp的和）/ W；(爬楼梯得到总楼梯数为i的概率）
当K < i < K + W时，那么在这次的前一次的点数范围是[i - W, K - 1]。我们的dp数组表示的是得到点i的概率，所以dp[i]=(dp[K-1]+dp[K-2]+…+dp[i-W])/W.（可以从前一次的基础的上选[1,W]个数字中的一个）
当i>=K+W时，这种情况下无论如何不都应该存在的，所以dp[i]=0.


https://leetcode.com/problems/new-21-game/discuss/132358/Java-O(K-+-W)-DP-solution-with-explanation

Firstly I came up with a basic DP solution which cost O((K + W) * W) time and it runs TLE:

class Solution {
    public double new21Game(int N, int K, int W) {
        if (K == 0) {
            return 1;
        }
        int max = K + W - 1;
        double[] dp = new double[max + 1];
        dp[0] = 1;
        for (int i = 1; i <= max; i++) {
            for (int j = 1; j <= W; j++) {
                if (i - j >= 0 && i - j < K) {
                    dp[i] += dp[i - j] / W;
                }
            }
        }
        double result = 0;
        for (int i = K; i <= N; i++) {
            result += dp[i];
        }
        return result;
    }
}

Then I realize that the transition equation dp[i] = (dp[i - W] + dp[i - W + 1] + ... + dp[i - 1]) / W could be simplified to dp[i] = (sum[i - 1] - sum[i - W - 1]) / W.

Furthermore, if we use dp[i] to directly represent the sum[i], we can get dp[i] = dp[i - 1] + (dp[i - 1] - dp[i - W - 1]) / W. This equation takes us to the final O(K + W) solution. Just take care with the beginning and the end of the array.

    public double new21Game(int N, int K, int W) {
        if (K == 0) {
            return 1;
        }
        int max = K + W - 1;
        double[] dp = new double[max + 1];
        dp[0] = 1;
        for (int i = 1; i <= max; i++) {
            dp[i] = dp[i - 1];
            if (i <= W) {
                dp[i] += dp[i - 1] / W;
            } else {
                dp[i] += (dp[i - 1] - dp[i - W - 1]) / W;
            }
            if (i > K) {
                dp[i] -= (dp[i - 1] - dp[K - 1]) / W;
            }
        }
        return dp[N] - dp[K - 1];
    }

https://leetcode.com/problems/new-21-game/discuss/132334/One-Pass-DP

In a word,
dp[i]: probability of get points i
dp[i] = sum(last W dp values) / W

    public double new21Game(int N, int K, int W) {
        if (K == 0 || N >= K + W) return 1;
        double dp[] = new double[N + 1],  Wsum = 1, res = 0;
        dp[0] = 1;
        for (int i = 1; i <= N; ++i) {
            dp[i] = Wsum / W;
            if (i < K) Wsum += dp[i]; else res += dp[i];
            if (i - W >= 0) Wsum -= dp[i - W];
        }
        return res;
    }




It is clear that the probability that Alice wins the game is only related to how many points x she starts the next draw with, so we can try to formulate an answer in terms of x.

Algorithm

Let f(x) be the answer when we already have x points. Clearly, f(x) = 1.0 when K <= x <= N, and f(x) = 0.0 when x > N.

We can write a recursion, $f(x) = \frac{1}{W}\big( \sum_{i=1}^W f(x+i) \big)$.

With naive dynamic programming, this leads to a $O(K * W + (N-K))$ solution: for each state k < K in decreasing order, we'll use the recursion to calculate f(k), doing $O(W)$ work each time. This is not efficient enough.

However, the sums for f(x) and f(x-1) are related: namely, $f(x) - f(x-1) = \frac{1}{W} \big( f(x+W) - f(x) \big)$. This allows us to calculate f(k-1) from f(k) in $O(1)$ time, by maintaining the numerator $S = \sum_{i=1}^W f(x+i)$.

Note that we can reduce the time complexity to $O(\max(K, W))$ and the space complexity to $O(W)$ by only keeping track of the last $W$ values of dp, but it isn't required.

    public double new21Game(int N, int K, int W) {
        double[] dp = new double[N + W + 1];
        for (int k = K; k <= N; ++k)
            dp[k] = 1.0;

        double S = Math.min(N - K + 1, W);
        for (int k = K - 1; k >= 0; --k) {
            dp[k] = S / W;
            S += dp[k] - dp[k + W];
        }
        return dp[0];
    }

https://blog.csdn.net/qq_20141867/article/details/81261711
    def new21Game(self, N, K, W):
        """
        :type N: int
        :type K: int
        :type W: int
        :rtype: float
        """
        if K == 0: return 1
        dp = [1.0] + [0.0] * N
        # Wsum表示(前W个dp之和)/W
        Wsum = 1.0000
        for i in range(1, N + 1):
            dp[i] = Wsum / W
            # 因为当i>=K时，不能再取数，因此后面的概率不能累加
            if i < K: Wsum += dp[i]
            # 因为只需要计算前w个dp之和，所以当i>=W时，减去最前面的dp。
            if 0 <= i - W < K: Wsum -= dp[i - W]
        return sum(dp[K:])

X. https://github.com/WuLC/LeetCode/blob/master/Algorithm/Python/837.%20New%2021%20Game.py

# recursive with cache, TLE
class Solution(object):     
    def new21Game(self, N, K, W):
        """
        :type N: int
        :type K: int
        :type W: int
        :rtype: float
        """
        self.cache = {}
        base = 1.0/W
        def helper(curr, N, K, W):
            if curr > N:
                return 0
            if K <= curr <= N:
                return 1
            if curr not in self.cache:
                prob = 0
                for i in xrange(1, W+1):
                    if curr+i > N:
                        break
                    if curr+i not in self.cache:
                        self.cache[curr+i] = helper(curr+i, N, K, W)
                    prob += base*self.cache[curr+i]
                self.cache[curr] = prob
            return self.cache[curr]
        return helper(0, N, K, W)