New 21 Game
Medium · Dynamic Programming · about 30 minutes
Asked at Google, Amazon, Microsoft.
Alice starts with 0 points and keeps drawing while she has fewer than k points; each draw adds an integer from 1..maxPts uniformly at random. Return the probability that she ends with at most n points. Answers within 10⁻⁵ are accepted.