some interesting math problem

1 min read

New 21 Game (math and 1D-DP)

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

  • 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.

Notice

  1. 0≤K≤N≤10000
  2. 1≤W≤10000
class Solution:
    """
    dp[i] represents the total probability to get points i,
    dp[i] = dp[1] * 1/W + dp[2] * 1/W + dp[3] * 1/W + ... dp[i-2] * 1/W + dp[i-1] * 1/W
    So dp[i] = (dp[1] + dp[2] + ... + dp[i - 1]) / W = Wsum / W
    Conditional probability: keep a window with size K (assume K = 10), the probability of getting point i is the sum of probability from point i - 10 to i, point i - 9 to i, ... , i -1 to i. Since every card has equal probability,
    the probability to get any one of cards is 1/10. So the total probability of dp[i] is sum of all conditional probability.
    Once i is over than or equal to K, we can accumulate probability to final result.
    """
    def new21Game(self, N, K, W):
        if K == 0 or N >= K + W: return 1
        dp = [1.0] + [0.0] * N
        Wsum = 1.0
        for i in range(1, N + 1):
            dp[i] = Wsum / W
            if i < K: Wsum += dp[i]
            if i - W >= 0: Wsum -= dp[i - W]
        return sum(dp[K:])