[Ruby] Reverse solution, with image examplanation step by step
Intuition\n\nSupposing $n = 5, k = 4, maxPts = 5$.\n\nwe use an array result[] to represent:\n\n\n  result[x] := The probability that we finally have less or eq
# Intuition\n\nSupposing $n = 5, k = 4, maxPts = 5$.\n\nwe use an array `result[]` to represent:\n\n```\n  result[x] := The probability that we finally have less or equal than n points \n    when we currently have x points in hand\n      and we draw cards till we have k points\n```\n\nBy that definition:\n  1. When we have $4$ points, we can not draw any more, and the probability having less or equal than $5$ points is $1.0$\n  2. When we have $5$ points, we can not draw any more, and the probability having less or equal than $5$ points is $1.0$\n  3. When we have $6$ points, we can not draw any more, and the probability having less or equal than $5$ points is $0.0$\n  4. ...\n\nLet\'s puts this in the image below:\n\n\n![image.png](https://assets.leetcode.com/users/images/ff30417d-65a9-4a06-98c9-b7adb9cd5a51_1673801370.8167605.png)\n\nWhat will happen when we have 3 points in hand?\n\n1. We have $1/5$ probability to get 1 point and reach $4$;\n2. We have $1/5$ probability to get 2 points and reach $5$;\n3. We have $1/5$ probability to get `3/4/5` points and reach `6/7/8`, but already goes over 5;\n\nBy this we get:\n\n$$\nresult[3] = \\frac{1}{5} \\times result[4] + \\frac{1}{5} \\times result[5] + ... + \\frac{1}{5} \\times result[8]\n\n= \\frac{1}{5} \\times (result[4]+result[5]+ result[6] + result[7] + result[8])\n$$\n\n```\nresult[3] = 0.4\n```\n\n![image.png](https://assets.leetcode.com/users/images/9cb124b7-bd74-45f1-a4f4-9ccd255cb48e_1673802296.8097718.png)\n\nThen let\'s have look at `result[2]`:\n\n1. We have `1/5` chance to to 3 (calculated in previous step);\n2. We have `1/5` chance to go to either 4 or 5 (got by definition);\n3. We have `1/5` chance to go to either 6 or 7 (got by definition);\n\n$$\nresult[2] = \\frac{1}{5} \\times (result[3]+result[4]+ result[5] + result[6] + result[7])\n$$\n\n```\nresult[2] = 0.48\n```\n\nAnd loop until we get to result[0]:\n\n![image.png](https://assets.leetcode.com/users/images/3b0cf6c5-afce-4f0c-89e3-6dcde3971158_1673802746.310535.png)\n\nAs we\'ve defined, `result[0]` represents *the probability we will have less than or equal to n points when we have 0 points in hand, we continue drawing until we have at least k points*.\n\nThat\'s the answer.\n\n\n# Complexity\n- Time complexity: $$O(k+n)$$\n\n- Space complexity: $$O(k+maxPts)$$\n\n# Code\n```\n# @param {Integer} n\n# @param {Integer} k\n# @param {Integer} max_pts\n# @return {Float}\ndef new21_game(n, k, max_pts)\n  return 1 if k - 1 + max_pts <= n # We can never reach n when we stop at k\n\n  result = Array.new(k + max_pts, 0.0)\n\n  k.upto(n) do |i|\n    result[i] = 1\n  end\n\n  sum = result[k...(k+max_pts)].sum\n\n  (k-1).downto(0) do |i|\n    result[i] = sum / max_pts\n    sum += result[i] - result[i+max_pts]\n  end\n\n  result[0]\nend\n```
['Math', 'Dynamic Programming', 'Sliding Window', 'Ruby']