Javascript solution O(N) with explanation (and math proof)
Based on Lee\'s post: https://leetcode.com/problems/new-21-game/discuss/132334/One-Pass-DP-O(N), I figured out a way to understand the solution. Hopefully you f
Based on Lee\'s post: https://leetcode.com/problems/new-21-game/discuss/132334/One-Pass-DP-O(N), I figured out a way to understand the solution. Hopefully you find the thought process to be intuitive.\n\nAssume we have:\n```\nmax = 10, k = 12, n = 15\n```\nSince max is 10, probability of drawing any card is `0.1`.\n\nThe DP array, or I\'ll call it `P[i]` below, contains probability of reaching sum `i` at some point of the game.\n\n===== Let\'s list out P0 to P15 one by one... =====\n\nNote: below 3 cases are not mutually exclusive. Also k can be smaller than max, but the logic won\'t change.\n\nCase 1:\nif i <= k, always add 1.1P(i-1) to P(i). Proof:\n```\nP0 = 1 // initialization\nP1 = 0.1 // getting card 1\'s chance is 0.1\nP2 = 0.1P1 + 0.1P0 = 1.1P1 // chance of getting card 1 then 1 again is 0.1P1, chance of getting card 2 is 0.1P0, adding them together we have 1.1P1\nP3 = 0.1P2 + 0.1P1 + 0.1P0 = 1.1P2 // same, getting card 2 then 1, or, getting card 1 then 2, or, getting card 3\n...\n...\nP10 = 1.1P9  // i reaches max\n```\n\nCase 2:\nif i > max, remove 0.1P(i - max - 1) from P(i). This is essentially a sliding window problem:\n```\nP11 = 0.1P10 + 0.1P9 + ... + 0.1P1 = 1.1P10 - 0.1P0\nP12 = 0.1P11 + 0.1P10 + ... + 0.1P2 = 1.1P11 - 0.1P1 // no more P1 because getting sum1 requires we draw card 11 - impossible\n```\n\nCase 3:\nif i > k, sliding window\'s right stops growing, meaning always add P(i-1) instead of 1.1P(i-1) to P(i):\n```\nP13 = 0.1P11 + 0.1P10 + ... + 0.1P3 = P12 - 0.1P2   // no longer add 0.1P12, because reaching 12 ends the game. Sliding window\'s left stops at 0.1P11\nP14 = P13 - 0.1P3   // remember to keep removing 0.1P3 as i=14 satisfies both case 2 and case 3\n```\n\nCode:\n```\nvar new21Game = function(n, k, maxPts) {\n    if (k+maxPts <= n || k===0) return 1;\n\n    let dp = [];\n    dp[0] = 1;\n    dp[1] = 1/maxPts;\n    \n    for (let i = 2; i <= n; i++) {\n        dp[i] = 0;\n        \n        if (i <= k) {\n            dp[i] = (1 + 1/maxPts) * dp[i-1];\n        } else {\n            dp[i] = dp[i-1];\n        }\n        if (i > maxPts) {\n            dp[i] -= dp[i-maxPts-1] / maxPts;\n        }\n    }\n    \n    return dp.reduce((acc, cur, idx) => {\n        if (idx >= k) {\n            acc += cur;\n        }\n        return acc;\n    }, 0)\n};\n```\n
['Math', 'Dynamic Programming', 'Sliding Window', 'JavaScript']