0837. 新 21 点【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 动态规划

1. 📝 题目描述

• leetcode

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

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

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

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

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

---

示例 1：

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

示例 2：

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

示例 3：

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

---

提示：

• 0 <= k <= n <= 10^4
• 1 <= maxPts <= 10^4

2. 🎯 s.1 - 动态规划

c

double new21Game(int n, int k, int maxPts) {
    if (k == 0 || n >= k - 1 + maxPts) return 1.0;
    double* dp = (double*)calloc(n + 1, sizeof(double));
    dp[0] = 1.0;
    double sum = 1.0, res = 0.0;
    for (int i = 1; i <= n; i++) {
        dp[i] = sum / maxPts;
        if (i < k) sum += dp[i]; else res += dp[i];
        if (i >= maxPts) sum -= dp[i - maxPts];
    }
    free(dp);
    return res;
}

js

/**
 * @param {number} n
 * @param {number} k
 * @param {number} maxPts
 * @return {number}
 */
var new21Game = function (n, k, maxPts) {
  if (k === 0 || n >= k - 1 + maxPts) return 1
  const dp = new Array(n + 1).fill(0)
  dp[0] = 1
  let sum = 1,
    res = 0
  for (let i = 1; i <= n; i++) {
    dp[i] = sum / maxPts
    if (i < k) sum += dp[i]
    else res += dp[i]
    if (i >= maxPts) sum -= dp[i - maxPts]
  }
  return res
}

py

class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        if k == 0 or n >= k - 1 + maxPts:
            return 1.0
        dp = [0.0] * (n + 1)
        dp[0] = 1.0
        s = 1.0
        res = 0.0
        for i in range(1, n + 1):
            dp[i] = s / maxPts
            if i < k:
                s += dp[i]
            else:
                res += dp[i]
            if i >= maxPts:
                s -= dp[i - maxPts]
        return res

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

算法思路：

• $dp[i]$ 表示得到 i 分的概率，当 $i<k$ 时 $dp[i]=\frac{1}{W}\sum _{j=1}^{W}dp[i-j]$
• 用滑动窗口维护前 W 个 dp 值的和，避免重复计算