Monte Carlo Simulations
Disclaimer: this solution does not pass the test as the required precision is 10^-5, but for real applications, it gives quite a interesting insight. Also this 
Disclaimer: this solution does not pass the test as the required precision is 10^-5, but for real applications, it gives quite a interesting insight. Also this is more a solution towards statistics than Software Engineer. Nonetheless, I think it\'s interesting to know different approaches:\n\n```\nimport random\nclass Solution:\n    def new21Game(self, N: int, K: int, W: int) -> float:\n        """\n        Start with 0 points. \n        Draws points uniformly distributed in [1, W] while total points < K  \n       \n\t\tMore specifically we are looking for "the probability that she has N or less points"\n\t\tLet\'s call X the random variable that takes 2 values {Alice has points <=N, Alice has points >N}. This is a Bernouilli random variable with parameter p (p being the value we are trying to find).\n\t\tProbability(Alice has points <= N) = p\n\t\tProbability(Alice has points > N) = 1 - p\n\t\tThe Law of large number tell us that the empirical mean ((x1 + x2 + ... + xn) / n) converges to the expected value as n goes to infinity.\n\t\tThe expected value of a Bernouilli random variable is exaclty what the parameter p is\n\t\tMonte Carlo Simulations give us an approximation of the expected value:\n\t\t(Provided that the numbers of simulation is big enough cf Law of large numbers)\n        """\n        def simulation(N, K, W):\n            points = 0\n            while points < K:\n                points += random.randint(1, W)\n            if points <= N:\n                return 1\n            return 0\n        \n        sample_size = 100000\n        total_time_points_smallest_than_N = 0\n        for i in range(sample_size):\n            total_time_points_smallest_than_N += simulation(N, K, W)\n        return total_time_points_smallest_than_N / sample_size\n    \n```\n\nRuntime: ~ O(sample_size * K)\nSpace: ~ O(1)\n\n\n\nTop Down Recursion with Memoization:\n\n```\ndef helper(N: int, K: int, W: int, P: int, memo: dict) -> float:\n\tif P in memo.keys():\n\t\treturn memo[P]\n\tif P < K:\n\t\tres = []\n\t\tfor new_point in range(1, W+1):\n\t\t\tres.append(helper(N, K, W, P + new_point, memo))\n\t\tmemo[P] = sum(res) / W\n\telse:\n\t\tmemo[P] = 1.0 if P <= N else 0.0\n\n\treturn memo[P]\n\nreturn helper(N, K, W, 0, {})\n```\n
[]