837.md

837 New 21 Game

Description

link

---

Solution : DP

dp[i] : the probability to reach point i

Recursive : dp[i] = sum(last W dp values) / W

---

Code

Complexity T : O(N) M : O(N)

class Solution:
    def new21Game(self, N, K, W):
        """
        :type N: int
        :type K: int
        :type W: int
        :rtype: float
        """
        if K == 0 or N >= K + W: return 1 # not possible
        
        # dp[i] = sum(last W dp values) / W
        dp = [1.0] + [0.0] * N # the probability to reach point i
        
        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:])