✅ Intuitive solution – even if you're bad at Dynamic Programming
Intuition\nI thought it was much more intuitive to take this problem backwards.\n\nLet\'s say that maxPts = 6, k = 5, and n = 7.\n\nThat means that Alice rolls 
# Intuition\nI thought it was much more intuitive to take this problem *backwards*.\n\nLet\'s say that `maxPts = 6`, `k = 5`, and `n = 7`.\n\nThat means that Alice rolls a dice each turn, and if her total ends up between 5 and 7 she wins. Any higher than 7 and she loses.\n\nThis smells like dynamic programming, so let\'s see if we can find an easy solution for some given input.\n\nIf Alice had exactly 4 points, we know that she will only roll the dice 1 more time. If she rolls `[1, 2, 3]`, she wins, and if she rolls `[4, 5, 6]`, she loses. So the chance of her winning from 4 points is `0.5`.\n\nHow can we generalize this? My solution was to consider the base cases - if Alice has 5 points, she\'s already won, so the chance of her winning is `1.0`. If she has 8 points, she\'s already lost, so the chance of her winning is `0.0`.\n\nLet\'s make a number line:\n```\nAlice\'s points: 0   1   2   3   4    5  6  7  8  9  10\nChance to win:  ?   ?   ?   ?   0.5  1  1  1  0  0  0\n```\n\nYou\'ll notice that when Alice has 4 points, she has an equal chance of landing on any of the numbers from 5 => 10 on her next roll. Therefore, we can take the average of the probability of the values from 5 => 10 to find her chance of winning when she\'s at 4 points.\n\nWe find that `average([1, 1, 1, 0, 0, 0]) = 0.5`, which lines up with our intuition before.\n\nThen, we can do the same thing for 3 points. She has a 1/6 chance of rolling a 1, bringing her total to 4, which we know will end up with her having a 0.5 chance to win. If she rolls `[2, 3, 4]`, she\'ll win, and if she rolls `[5, 6]`, she loses.\n\nSo, we can say that her total chance of winning at 3 points is \n```\n1/6 * (0.5 + 1 + 1 + 1 + 0 + 0) = 0.583\n```\n\nWe put this into the list of probabilities, and can now work our way backwards all the way to 0 points, which will be the answer (her chance of winning at the very start of the game).\n\n# Approach\nFor my solution, I initialized an array like `[1, 1, 1, 0, 0, 0]`, then calculated the probability for the next lowest value. We don\'t need to remember more values outside of our 6-length window, so we can just push the new value into the beginning of the array and pop the oldest value off the end.\n\nWe also need to account for some edge cases \u2013 if `k == 0`, Alice already wins without rolling anything, so we return `1.0`.\n\nAlso, if our "window" to win is big enough, we also can immediately return `1.0`. For instance, if we\'re rolling a dice and we have to hit between 3 and 13, we know that we\'ll never "bust" and go over 13.\n\n# Complexity\n- Time complexity:\n`O(n)`\n\n- Space complexity:\n`O(maxPts)`\n\n# Code\n```\nclass Solution {\n    func new21Game(_ n: Int, _ k: Int, _ maxPts: Int) -> Double {\n        if k == 0 { return 1.0 }\n        if n - k >= maxPts { return 1.0 }\n\n        let goodRollCount = n - k + 1\n        var chances = [Double](repeating: 1, count: goodRollCount)\n                       + [Double](repeating: 0, count: maxPts - goodRollCount)\n\n        var result = 0.0\n        var sum = chances.reduce(0) { $0 + $1 }\n\n        for _ in 0..<k {\n            result = sum / Double(chances.count)\n            sum -= chances.popLast()!\n            sum += result\n            chances.insert(result, at: 0)\n        }\n\n        return result\n    }\n}\n```
['Swift']