New 21 Game LeetCode solution in C++

1
class Solution {
2
 public:
3
  double new21Game(int n, int k, int maxPts) {
4
    if (k == 0 || n >= k + maxPts - 1) return (double)1;
5
    vector<double> dp(n + 1);
6
    dp[0] = 1;
7
    double sum = 0;
8
    for (int i = 0; i < n; i++) {
9
      if (i < k) sum += dp[i]; // reach f(2) by directly drawing f(2) or f(1) and f(1)
10
      if (i >= maxPts) sum -= dp[i - maxPts];
11

12
      dp[i + 1] = sum / maxPts;
13
    }
14
    double ret = 0;
15
    for (int i = k; i <= n; i++) ret += dp[i];
16
    return ret;
17
  }
18
};