题目 ​

爱丽丝参与一个大致基于纸牌游戏 “21 点” 规则的游戏，描述如下：

爱丽丝以 0 分开始，并在她的得分少于 k 分时抽取数字。 抽取时，她从 [1, maxPts] 的范围中随机获得一个整数作为分数进行累计，其中 maxPts 是一个整数。 每次抽取都是独立的，其结果具有相同的概率。

当爱丽丝获得 k 分 或更多分 时，她就停止抽取数字。

爱丽丝的分数不超过 n 的概率是多少？

与实际答案误差不超过  10-5 的答案将被视为正确答案。

示例 1：

输入：n = 10, k = 1, maxPts = 10
输出：1.00000
解释：爱丽丝得到一张牌，然后停止。

输入：n = 10, k = 1, maxPts = 10
输出：1.00000
解释：爱丽丝得到一张牌，然后停止。

示例 2：

输入：n = 6, k = 1, maxPts = 10
输出：0.60000
解释：爱丽丝得到一张牌，然后停止。 在 10 种可能性中的 6 种情况下，她的得分不超过 6 分。

输入：n = 6, k = 1, maxPts = 10
输出：0.60000
解释：爱丽丝得到一张牌，然后停止。 在 10 种可能性中的 6 种情况下，她的得分不超过 6 分。

示例 3：

输入：n = 21, k = 17, maxPts = 10
输出：0.73278

输入：n = 21, k = 17, maxPts = 10
输出：0.73278

提示：

• 0 <= k <= n <= 104
• 1 <= maxPts <= 104

理解题目 ​

首先爱丽丝的低分是 0 分，开始从【1，W】中随机抽取分数，抽取到的分数一直累加，一直累加至 K 分或者 k 分以上的时候就停止抽取分数，这个时候 K 分不超过 N 分的概率是多少

题解 ​

想象一下，如果说我使用的是示例 3，当最大达到什么分数时还可以抽牌呢，答案是 16 ，从【1,10】中抽取任意一张牌不超过 21 的有 1,2,3,4,5，超过的有 6,7,8,9,10。所以 n=16 时，再抽取一张牌的分数不超过 21 的概率为 0.5

再看当 n=15 时，从【1,10】中抽取任意一张牌不超过 21 的有 1,2,3,4,5,6,超过的有 7,8,9,10。当抽到 1 时 n=16 还可以再抽牌，所以两次抽取的概率相乘 0.1*0.5=0.05，其他的都超过 17 了不允许再抽牌了，所以 n=15 的不超过 21 分的概率为 0.55

再看当 n=14 时，从【1,10】中抽取任意一张牌不超过 21 的有 1,2,3,4,5,6,7,超过的有 8,9,10。当抽到 1 时 n=15 概率为 0.10.55,当抽取 2 时 n=16 概率为 0.10.5 其他的都超过 17 了不允许再抽牌了，所以 n=15 的不超过 21 分的概率为 0.605

由此可以得知

a16 = (1+1+1+1+1+0+0+0+0+0)/10 = 1/2
a15 = (a16+1+1+1+1+1+0+0+0+0)/10 = 0.55
a14 = (a15+a16+1+1+1+1+1+0+0+0)/=0.605
.
.
.
a(x+1)=(a(x+2)+a(x+3)+......+a(x+w+1))/10
a(x)=(a(x+1)+a(x+2)+a(x+3)+......+a(x+w))/10

a16 = (1+1+1+1+1+0+0+0+0+0)/10 = 1/2
a15 = (a16+1+1+1+1+1+0+0+0+0)/10 = 0.55
a14 = (a15+a16+1+1+1+1+1+0+0+0)/=0.605
.
.
.
a(x+1)=(a(x+2)+a(x+3)+......+a(x+w+1))/10
a(x)=(a(x+1)+a(x+2)+a(x+3)+......+a(x+w))/10

根据a(x)-a(x+1)可以得出我们的状态转移方程为a(x)=(a(x+1)-a(x+w+1))/10 + a(x+1)

答案 ​

function new21Game(n: number, k: number, maxPts: number): number {
  if (k === 0) return 1.0;
  let dp = new Array(k + maxPts).fill(0);
  for (let i = k; i <= n; i++) {
    dp[i] = 1.0;
  }
  dp[k - 1] = (1.0 * Math.min(n - k + 1, maxPts)) / maxPts;
  for (let i = k - 2; i >= 0; i--) {
    dp[i] = dp[i + 1] + (dp[i + 1] - dp[i + maxPts + 1]) / maxPts;
  }
  return dp[0];
}

function new21Game(n: number, k: number, maxPts: number): number {
  if (k === 0) return 1.0;
  let dp = new Array(k + maxPts).fill(0);
  for (let i = k; i <= n; i++) {
    dp[i] = 1.0;
  }
  dp[k - 1] = (1.0 * Math.min(n - k + 1, maxPts)) / maxPts;
  for (let i = k - 2; i >= 0; i--) {
    dp[i] = dp[i + 1] + (dp[i + 1] - dp[i + maxPts + 1]) / maxPts;
  }
  return dp[0];
}