Leetcode Problem 837. New 21 Game

Algorithm

1. Initialize an array dp of size n + 1 with zeros.
2. Set dp[0] = 1 as the base case.
3. Initialize a variable s with 1 if k > 0, otherwise with 0.
4. Iterate over i from 1 to n:
   • Set dp[i] = s / maxPts.
   • If i < k, add dp[i] to s.
   • If i - maxPts >= 0 and i - maxPts < k, subtract dp[i - maxPts] from s.
5. Return the sum of dp[i] for all k <= i <= n.