New 21 Game || C++ || DP || DSA
Intuition\n Describe your first thoughts on how to solve this problem. \n Concept of Dynamic programming is used to solve this problem.\n\n# Approach\n Describe
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n* Concept of Dynamic programming is used to solve this problem.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n* O(N)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n* O(N)\n\n# Code\n```\nclass Solution {\n public:\n  double new21Game(int n, int k, int maxPts) {\n    // When the game ends, the point is in [k..k - 1 + maxPts]\n    //   P = 1, if n >= k - 1 + maxPts\n    //   P = 0, if n < k (note the constraints already have k <= n)\n    if (k == 0 || n >= k - 1 + maxPts)\n      return 1.0;\n\n    double answer = 0.0;\n    vector<double> dp(n + 1);  // dp[i] := prob to have i points\n    dp[0] = 1.0;\n    double windowSum = dp[0];  // P(i - 1) + P(i - 2) + ... + P(i - maxPts)\n\n    for (int i = 1; i <= n; ++i) {\n      // The prob to get point i is\n      // P(i) = [P(i - 1) + P(i - 2) + ... + P(i - maxPts)] / maxPts\n      dp[i] = windowSum / maxPts;\n      if (i < k)\n        windowSum += dp[i];\n      else  // The game ends\n        answer += dp[i];\n      if (i - maxPts >= 0)\n        windowSum -= dp[i - maxPts];\n    }\n\n    return answer;\n  }\n};\n\n```
['C++']