aboutsummaryrefslogtreecommitdiff
path: root/new_21_game.py
blob: cc634d0f633bd37a88dc06e495ddfed1ad464668 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
# 837. 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 range
'[1, maxPts]', where 'maxPts' is an integer. each draw is independent and
the outcomes have equal posibilities. 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(object):
    def new21Game(self, n, k, maxPts):
        """
        :type n: int
        :type k: int
        :type maxPts: int
        :rtype: float
        """
        if k == 0 or n >= k + maxPts:
            return 1
        dp = [1.0] + [0.0] * n
        sum = 1.0
        for i in range(1, n + 1):
            dp[i] = sum / maxPts
            if i < k:
                sum += dp[i]
            if i - maxPts >= 0:
                sum -= dp[i - maxPts]
        return sum(dp[k:])


if __name__ == "__main__":
    obj = Solution()
    print(obj.new21Game(n=10, k=1, maxPts=10))
    print(obj.new21Game(n=6, k=1, maxPts=10))
    print(obj.new21Game(n=21, k=17, maxPts=10))