Math solution: O(k) time, O(maxPts) space, explained
Explanation\nHere we\'ll call maxPts a dice, since it is essentially one. (Yep, 1d10000 would make a big die, not for a casual DnD game).\n\nImagine Alice getti
# Explanation\n*Here we\'ll call `maxPts` a dice, since it is essentially one. (Yep, 1d10000 would make a big die, not for a casual DnD game).*\n\nImagine Alice getting points as traverse through the integers left to right, from 0 to the values of k and n.\n\n\u2026\u2007$k-2$\u2007\u2007\u2007$k-1$\u2007\u2007\u2007**k\u2007\u2007\u2007\u2026\u2007\u2007\u2007n**\u2007\u2007\u2007$n+1$\u2007\u2026 \n\nThe numbers above represent possible points scores during the game. Take a look at the bolded interval \u2013 that\'s where Alice needs to land for a win. Less than $k$ means the game would still go on, and scores more than $n$ would be a bust. The count of integers on that interval (including borders) is $n - k + 1$, denote this number as $winLength$.\n\nLet\'s think about possible situations where Alice can get into it on her next move. Obviously, she is somewhere in the range of $dice$ points before $k$, (no below that, or even the maximum dice roll would not be enough, and no further, since then the game is already over). Denote Alice\'s current position (i.e. her score) as $cur$. What is the chance that her next turn will bring her to the winning score? Since all dice rolls are of equal probability, the odds are as follows:\n\n*(the count of positions inside the winning interval that are reachable with the die roll) / (the count of all possible positions after the move)*\n\nThe divisor is not difficult to determine \u2013 $dice$ possible roll values mean $dice$ possible outcomes. What can be said about the divisible? Since we are at position $cur$, the farthest reachable point is $cur + dice$. If it lies inside the interval, then the number of reachable positions between it and $k$ is equal to **(cur + dice) - k + 1**. This is almost a ready value for the divisor, we only need to consider possible constraints and boundary cases. Obviously, the number of reachable values in an interval cannot be greater than the interval itself. Hence, the upper bound for it is $n - k + 1$, i.e. **winLength**. Indeed, if the current position and the size of the dice allow, we can hit any point in the interval, no more than that. The lower bound will be **0** \u2013 if we are far on the left, with a small dice it may not be possible to reach the interval at all. This restriction extends the scope of the resulting formula as far to the left as we wish, i.e. all the way to zero.\n\nSo! We got the formula for **probability of hitting the win on the next move**: min((n - k + 1), max(0, cur + dice - k + 1)) / dice, or simply put, **clamp(0, (cur + dice - k + 1), winLength) / dice** and we know that it is valid for any score $cur$.\n\nLets consider the case where Alice is one point before $k$, i.e. $cur = k - 1$. The game will end on the following turn in any event, and the chance to win is $clamp(0, dice, winLength) / dice$. Lets call it $Chance_{k-1}$.\nNow we consider the position $$cur = k - 2$$. The chance to get from there directly into the winning interval is still determined by the formula. However, now there is an additional possibility that we will hit $$k - 1$$ first, and the game will continue. The probability of hitting it (as well as any position in the range of the dice roll) is $$1/dice$$. If we get there, we already know the probability of winning from here, it\'s $$Chance_{k-1}$$. Thus, the value $$Chance_{k-2}$$ of winning for position $$k-2$$ is equal to the probability of getting right into the interval + the odds of landing on $$k - 1$$, multiplied by the probability of winning it: $Chance_{k-2} = clamp(0, dice - 1, winLength) / dice + (1 / dice) * Chance_{k-1} = (clamp(0, dice - 1, winLength) + Chance_{k-1}) / dice$.\nLets examine the preceding position as well, $cur=k-3$. There are now two possible positions ahead before the winning interval, for each of them the probability of victory has already been calculated, and the chance of hitting each on the current turn is equal to $1/dice$. So, $Chance_{k-3} = (clamp(0, dice - 2, winLength) + Chance_{k-1} + Chance_{k-2}) / dice$.\nLet\'s move on like that until we reach the starting position of zero points and write out the values in order, so that the sequence rule is clear:\n\n$Chance_{k-1} = clamp(0, dice, winLength) / (dice)$\n$Chance_{k-2} = (clamp(0, dice - 1, winLength) + Chance_{k-1}) / dice$\n$Chance_{k-3} = (clamp(0, dice - 2, winLength) + Chance_{k-1} + Chance_{k-2}) / dice$\n\u2026\n$Chance_{(k-1)-i} = (clamp(0, dice - i, winLength) + \\sum_{j=1}^{min(i, dice)}Chance_{k-j}) / dice$\n\nWhy the sum is limited to no more than $dice$ of previous Chances and not all of them? Remember, as previously stated: "the probability of hitting any position *in the dice roll range* is $1/dice$". As we examine the points more and more to the left, the positions go out of range of the die roll, become unreachable, and the probability of hitting them on the next turn is zero, contributing nothing to the overall chance.\n\n*Math is over, congratulations to all who\'ve made it through to this point.*\n\n# Approach\nSo, we apply the formula derived above to calculate the odds of winning, sequentially from a score of $k-1$ downto $0$ in the dynamic programming manner. We are changing `i` from `0` to `k-1` inclusive, thus getting the calculation of $Chance_{k-1}$ at the first iteration and $Chance_{0}$ at the last iteration \u2013 the probability of winning for the starting 0 points, which is what we need.\n\nDuring the iterations we use the Queue with max size of $dice$ as a sliding window to the last $dice$ calculated chances and update the computed sum of said chances as we go, by adding newly obtained and subtracting the oldest, $(dice+1)$-th one.\n\n\n# Complexity\n- Time complexity: $\u0398(k)$\n$k$ iterations, no more, no less.\n- Space complexity: $\u0398(min(k, maxPts))$\nJust the queue holding up to maxPts of elements, and a couple of variables.\n\n```swift []\nclass Solution {\n    func new21Game(_ n: Int, _ k: Int, _ maxPointsPerDraw: Int) -> Double\n    {\n        let dice = Double(maxPointsPerDraw), winLength = Double(n - k + 1)\n        \n         // already won  or  interval is so big we can\'t miss it\n        if     k == 0    ||   winLength >= dice { return 1.0 }\n\n        var chance = 0.0\n        var lastChances = Queue<Double>()\n        var lastChancesSum = 0.0\n        for i in 0..<k\n        {\n            chance = (clamp(mn: 0.0, dice - Double(i), mx: winLength) + lastChancesSum) / dice\n            lastChancesSum += chance\n            lastChances.enqueue(chance)\n            if lastChances.count > maxPointsPerDraw {\n                lastChancesSum -= lastChances.dequeue()!\n            }\n        }\n        return chance\n    }\n}\n\nclass Queue<T>\n{\n    var isEmpty: Bool { head == nil }\n    private(set) var count: Int = 0\n\n    func enqueue(_ val: T)\n    {\n        if let node = tail {\n            node.next = getNode(val)\n            tail = node.next\n        }\n        else {\n            head = getNode(val)\n            tail = head\n        }\n        count += 1\n    }\n    func enqueue<S>(_ s: S) where S : Sequence, S.Element == T {\n        s.forEach { element in enqueue(element) }\n    }\n\n    func dequeue() -> T?\n    {\n        if let node = head {\n            head = node.next\n            if head == nil { tail = nil } \n            count -= 1            \n            defer { node.next = nil; node.val = nil; nodeCache.append(node) }\n            return node.val\n        }\n        else { return nil }\n    }\n\n    private var head: QueueNode?\n    private var tail: QueueNode?\n    private var nodeCache: [QueueNode] = []\n    private func getNode(_ val: T) -> QueueNode {\n        if let node = nodeCache.popLast() {\n            node.val = val; return node\n        }\n        else { return QueueNode(val) }  \n    }\n\n    private class QueueNode {\n        var next: QueueNode?\n        var val: T!\n        init(_ val: T) { self.val = val }\n    }\n}\n\nfunc clamp<T: Comparable>(mn: T, _ value: T, mx: T) -> T  {\n    return min(max(value, mn), mx)\n}\n```\n```cpp []\nclass Solution {\npublic:\n    double new21Game(int n, int k, int maxPts)\n    {\n        double dice = maxPts, winLength = n - k + 1;\n        \n          // already won  or  interval is so big we can\'t miss it\n        if (    k == 0    ||    winLength >= dice ) { return 1; }\n\n        double chance = 0, lastChancesSum = 0;\n        queue<double> lastChances;\n\n        for (int i = 0; i < k; i++)\n        {\n            chance = (clamp(dice - i, 0.0, winLength) + lastChancesSum) / dice;\n            lastChancesSum += chance;\n            lastChances.push(chance);\n            if (lastChances.size() > dice) {\n                lastChancesSum -= lastChances.front();\n                lastChances.pop();\n            }\n        }\n    return chance;\n    }\n};\n```\n```java []\nclass Solution {\n    public double new21Game(int n, int k, int maxPts)\n    {\n        double dice = maxPts, winLength = n - k + 1;\n\n          // already won  or  interval is so big we can\'t miss it\n        if (    k == 0    ||    winLength >= dice ) { return 1; }\n\n        double chance = 0, lastChancesSum = 0;\n        Queue<Double> lastChances = new LinkedList<>();\n \n        for (int i = 0; i < k; i++)\n        {\n            chance = (clamp(dice - i, 0.0, winLength) + lastChancesSum) / dice;\n            lastChancesSum += chance;\n            lastChances.add(chance);\n            if (lastChances.size() > dice) {\n                lastChancesSum -= lastChances.remove();\n            }\n        }\n        return chance;\n    }\n\n    static double clamp(double val, double min, double max) {\n        return Math.max(min, Math.min(max, val));\n    }\n}\n```\n```python3 []\nfrom queue import Queue\nclass Solution:\n    def new21Game(self, n: int, k: int, dice: int) -> float:\n        winLength = n - k + 1\n\n        # if already won or interval is so big we can\'t miss it\n        if k == 0 or winLength >= dice:\n            return 1.0\n\n        chance = 0.0; lastChancesSum = 0.0\n        lastChances = Queue(maxsize = dice + 1)\n\n        for i in range(k):\n            chance = (clamp(dice - i, 0.0, winLength) + lastChancesSum) / dice\n            lastChancesSum += chance\n            lastChances.put(chance)\n            if lastChances.full():\n                lastChancesSum -= lastChances.get()\n\n        return chance\n    \ndef clamp(value, lower, upper):\n    return lower if value < lower else upper if value > upper else value\n```
['Math', 'Dynamic Programming', 'Swift', 'Sliding Window', 'Probability and Statistics']