✅ O(n) Easy Solution Explained
Approach\nThis solution applies dynamic programming to calculate the probability of Alice reaching a specific score. Initializing a DP array with the certainty 
# Approach\nThis solution applies dynamic programming to calculate the probability of Alice reaching a specific score. Initializing a DP array with the certainty of 0 points (probability of 1), it iteratively builds probabilities for scores from 1 to `n` by averaging the last `maxPtsd` scores.\n\nA `sum` variable tracks the sum of recent probabilities. When the score reaches Alice\'s stopping point `k`, these probabilities contribute to the final result.\n\nTo maintain `sum`, the solution deducts the probability of scores \'maxPtsd\' behind once exceeding `maxPtsd`. This guarantees `sum` only contains recent probabilities.\n\nUltimately, the solution provides the combined probability of Alice achieving `n` or less points, by summing probabilities from `k` to `n`.\n\n# Time Complexity\n**O(n)**\nThe runtime complexity for this solution is `O(n)`, where n is the maximum possible points Alice can achieve. This is because we are iterating over each point from 0 to n exactly once to build our dynamic programming array.\n\n# Space complexity\n**O(n)**\nThe space complexity is also `O(n)` due to the storage needed for the dynamic programming array that stores the probability for each point from 0 to n.\n\n# Solution\n```\nclass Solution {\n    func new21Game(_ n: Int, _ k: Int, _ maxPts: Int) -> Double {\n        if k == 0 || n >= k + maxPts { return 1.0 }\n\n        var dp = [Double](repeating: 0, count: n + 1)\n        dp[0] = 1.0\n        var sum = 1.0, res = 0.0\n        let maxPtsd = Double(maxPts)\n\n        for i in 1...n {\n            dp[i] = sum / maxPtsd\n            i < k ? (sum += dp[i]) : (res += dp[i])\n            i - maxPts >= 0 ? (sum -= dp[i - maxPts]) : ()\n        }\n\n        return res\n    }\n}\n```
['Dynamic Programming', 'Swift', 'Probability and Statistics']