Problem statement

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

Solution

There is a simple, but powerful trick, which can help us to solve this problem: we need to start from the end: that is define dp(x) be the answer if we gain x points. We can say, that f(x) = f(x+1) + f(x+2) + ... + f(x+W))/W. Also we can state, that dp[k] = 1 when K <= k <= N, else it is equal to 0. Finally, we need to go from K - 1 backwards and evaluate probabilities.

Complexity

Time complexity is O(N + W), because we can update average in O(1), space complexity is O(W).

Code

class Solution:
    def new21Game(self, N, K, W):
        dp = [0] * (N + W + 1)
        for k in range(K, N + 1): dp[k] = 1
        
        S = min((N - K + 1)/W, 1)
        
        for k in range(K - 1, -1, -1):
            dp[k] = S
            S += (dp[k] - dp[k + W])/W

        return dp[0]

Remark

In fact what we have here can be looked as it is Markov Chain.