837. New 21 Game

 

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

 

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, maxPts], where maxPts is an integer. Each draw is independent and the outcomes have equal probabilities.

Alice stops drawing numbers when she gets k or more points.

Return the probability that Alice has n or fewer points.

Answers within 10-5 of the actual answer are considered accepted.

class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        if k == 0 or n >= k + maxPts: return 1
        dp = [1.0] + [0.0] * n
        Wsum = 1.0
        for i in range(1, n + 1):
            dp[i] = Wsum / maxPts 
            if i < k: Wsum += dp[i]
            if i - maxPts >= 0: Wsum -= dp[i - w]
        return sum(dp[k:])

 

wSum = sum of last maxPts dp values 

dp[i] = the probability of reaching i

 

dp[n] = wSum / maxPts = sum([dp[n-maxPts, n-1]) / maxPts

-> To reach n, Alice should be in range [n-maxPts, n-1].