DP solution with Go (and explanation)
Let\'s take n = 21, k = 17, maxPts = 10 as an example\n\nThe finish state would be from 17 to 26 (as 16 will continue, and maximum draw will be 10)\n\nIf you\'r
Let\'s take n = 21, k = 17, maxPts = 10 as an example\n\nThe finish state would be from 17 to 26 (as 16 will continue, and maximum draw will be 10)\n\nIf you\'re currently in 16, what\'s the probability your final result less than n (21)? \nIt should be 0.5, as you can draw 1,2,3,4,5.  So, 5 / 10 = 0.5 as P(16)\n\nIf you\'re currently in 15, what\'s the probability your final result less than n (21)? \nit\'s when you draw 1 and then draw again and final result less than 21 which is the question above)\n      when you draw 2, 3, 4, 5, 6\nP(15) = 1/10 * P(16) + 1/10 * P(17) + 1/10 * P(18) ... + 1/10 * P(21) \n(P(17) to P(21) are all equal to 1 )\n\nSo the generalization\nP(i) is the probably that you\'re currently with i points, and your final result less than n\nP(i) = 1/maxPts * ( P(i+1) + P(i+2) ... + P(i + maxPts) )\n\nWe  start from P(k) and compute all the way to P(0) and P(0) is your answer\n\nwe need P[k + maxPts] size at most\nand in computation for P(i), we need Sum(P(i+1) to P(i+maxPts)), so we maintain\na sum. \n\nIn each iteration: \nP(i) = Sum / maxPts\nSum -= P(i+maxPts) // pop last element \nSum += P(i)\n\nThe Implementation\n```\nfunc new21Game(n int, k int, maxPts int) float64 {\n  // if n is big, then from dp[k] to dp[k-1+maxPts] should be 1, rest are zero \n  // if maxPts is big, then from dp[k] to dp[n] will be 1, rest are zero \n  // we don\'t need to record zeros\n  dp := make([]float64, min(n + 1, k + maxPts))\n  \n  // dp[i] = 1/maxPts * (dp[i+1] + dp[i+2] + dp[i+3] ... dp[i+maxPts])\n  // so we maintain sum = dp[i+1] ... dp[i+maxPts]\n  sum := 0.0 \n  for i := k; i <= min(n, k - 1 + maxPts); i++ {\n    dp[i] = 1.0\n    sum += dp[i]\n  }\n  \n  for i := k - 1; i >= 0; i-- {\n    dp[i] = sum / float64(maxPts)\n    \n    // remove the last element dp[i+maxPts] \n    // or if maxPts is too large, then it should be 0, we just ignore it\n    if i + maxPts < len(dp) {\n      sum -= dp[i+maxPts]\n    } \n    sum += dp[i] \n  }\n    \n  return dp[0]\n}\n\nfunc min(a, b int) int {\n  if a < b {\n    return a\n  }\n  \n  return b\n}\n```
[]