BinarySearch 0613 Probability Game

Problem statement

https://binarysearch.com/problems/Probability-Game/

Solution

Equal Leetcode 0837 New 21 Game, but check also case, where K > N.

Complexity

Time is O(N + W), space is O(W).

Code

class Solution:
    def solve(self, N, K, W):
        if K > N: return 0
        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]