Mathematical Intuition (Very Easy) || O(N) Time  Complexity || O(N) Space Complexity
Mathematical Intuition\n Describe your first thoughts on how to solve this problem. \nSince we can draw a number $a_i \leq maxPts$ any number of time before get
# Mathematical Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nSince we can draw a number $a_i \\leq maxPts$ any number of time before getting $k \\leq \\sum_{i=1}^{N} a_i \\leq n $. We can reframe the problem in the following way: \nGiven list of numbers $a_i$ where $ 1 \\leq a_i \\leq maxPts $ where $i \\in Z+$ . We want to find sum of $P(\\sum_{i=1}^{N} a_i = K)$ where k <=K <= n. [ note: N is not contrained here]. \n        \nWe can write $P(\\sum_{i=1}^{N} a_i = K) = \\sum_{z=1}^{maxpts} P(\\sum_{i=1}^{N-1} a_i = K-z) P(a_N = z)$ where for K-z < 0 probability is also zero.\n\nWe know that $P(a_N = Z) = 1/maxPts$ [$\\because$ all values are equiprobable] so $P(\\sum_{i=1}^{N} a_i = K) = 1/maxPts * \\sum_{z=1}^{maxpts} P(\\sum_{i=1}^{N-1} a_i = K-z)$\nSince N is not contrained here So we will omit N from equation and focus on probability where sum of any number of integers is equal to K so $dp[K] = P(\\sum_{i} a_i = K)$ \n\nWe can write above equation as $dp[k] = 1/maxpts *  \\sum_{z=1}^{maxpts} dp[K-z]$. Here dp[K-z] = 0 if K-z < 0 or K-z > k  \n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe approach is to simply code the last equation and sum the probabilities from k to n in \'dp\' array. Now the problem can be solved using dp.\n# Complexity\n- Time complexity: O(n) if we use sliding window to compute the sum $\\sum_{z=1}^{maxpts} dp[K-z]$ \n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public double new21Game(int n, int k, int maxPts) {\n        /**** MATHS  *******/\n        // Given k <= \\sum_{i=1}^{N} a_i <= n [ note: N is not contrained here]\n        // We want to find  P(\\sum_{i=1}^{N} a_i = K) where k <=K <= n\n        \n        // Now we can write P(\\sum_{i=1}^{N} a_i = K) = \\sum_{z=1}^{maxpts} P(\\sum_{i=1}^{N-1} a_i = K-z) P(a_N = z)\n\n        // We know that P(a_N = Z) = 1/maxPts [all values are equiprobable]\n\n        // so P(\\sum_{i=1}^{N} a_i = K) = 1/maxPts * \\sum_{z=1}^{maxpts} P(\\sum_{i=1}^{N} a_i = K-z)\n        // Since N is not contrained here So we will consider N = inf which will cover all the probability where sum of any number of integers is equal to K\n\n        // so dp[K] = P(\\sum_{i} a_i = K) \n\n        // We can write above equation as dp[k] = 1/maxpts *  \\sum_{z=1}^{maxpts} dp[K-z]\n        // Here dp[K-z] = 0 if K-z < 0 or K-z > k  \n\n        double dp[] = new double[n+1];\n        dp[0]=1.0;\n        double windowSum = 0;\n        for(int i=1;i<=n;i++){\n            /** Commented code is bit slow. We can implement the same using sliding window as well */\n            // for(int j = Math.max(0,i-maxPts);j<Math.min(i,k);j++){\n            //     dp[i] += dp[j];\n            // }\n            // dp[i] /=maxPts;\n            if(i-1 < k){\n                windowSum +=  dp[i-1];\n            }\n            if(i-maxPts-1>=0 && i-maxPts-1 < k ){\n                windowSum -= dp[i-maxPts-1];\n            }\n            dp[i] = windowSum/maxPts;\n        }\n        double sum=0;\n        for(int i=k;i<=n;i++){\n            sum+=dp[i];\n        }\n        return sum;\n    }\n}\n```
['Math', 'Dynamic Programming', 'Sliding Window', 'Java']