What is the main DP pattern in New 21 Game?

The core pattern is state transition dynamic programming, tracking the probability of each point total and accumulating over previous maxPts states.

Why use a sliding window in this problem?

Sliding window efficiently computes dp[x] by summing the previous maxPts probabilities in O(1) per step, avoiding O(n*maxPts) computation.

How do we handle k = 0 in New 21 Game?

If k = 0, Alice draws no cards and the probability of being at most n is 1, since she stops immediately.

Can this method handle large maxPts values?

Yes, sliding window ensures that even large maxPts do not lead to excessive computation, keeping time complexity linear in n.

How do we compute the final probability?

Sum dp[x] for all x between k and n inclusive, as these represent all possible outcomes where Alice stops at or below n points.

#837

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

新 21 点

爱丽丝参与一个大致基于纸牌游戏 “21点” 规则的游戏，描述如下：爱丽丝以 0 分开始，并在她的得分少于 k 分时抽取数字。抽取时，她从 [1, maxPts] 的范围中随机获得一个整数作为分数进行累计，其中 maxPts 是一个整数。每次抽取都是独立的，其结果具有相同的概率。当爱丽丝获得 …

数学动态规划滑动窗口概率与统计

题目描述

爱丽丝参与一个大致基于纸牌游戏 “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⁴
1 <= maxPts <= 10⁴

lightbulb

解题思路

方法一：记忆化搜索

我们设计一个函数 $dfs(i)$ ，表示当前分数为 $i$ 时，到最终停止抽取数字时，分数不超过 $n$ 的概率。那么答案就是 $dfs(0)$ 。

函数 $dfs(i)$ 的计算方法如下：

如果 $i \ge k$ ，那么停止抽取数字，如果 $i \le n$ ，返回 $1$ ，否则返回 $0$ ；
否则，可以在 $[1,..\textit{maxPts}]$ 范围内抽取下一个数字 $j$ ，那么 $dfs(i) = \frac{1}{maxPts} \sum_{j=1}^{maxPts} dfs(i+j)$ 。

这里我们可以使用记忆化搜索来加速计算。

以上方法的时间复杂度为 $O(k \times \textit{maxPts})$ ，会超出时间限制，我们需要优化一下。

当 $i \lt k$ 时，以下等式成立：

\begin{aligned} dfs(i) &= (dfs(i + 1) + dfs(i + 2) + \cdots + dfs(i + \textit{maxPts})) / \ & (1) \end{aligned}

当 $i \lt k - 1$ 时，以下等式成立：

\begin{aligned} dfs(i+1) &= (dfs(i + 2) + dfs(i + 3) + \cdots + dfs(i + \textit{maxPts} + 1)) / \textit{maxPts} & (2) \end{aligned}

因此，当 $i \lt k-1$ 时，我们将等式 $(1)$ 减去等式 $(2)$ ，得到：

\begin{aligned} dfs(i) - dfs(i+1) &= (dfs(i + 1) - dfs(i + \textit{maxPts} + 1)) / \textit{maxPts} \end{aligned}

即：

\begin{aligned} dfs(i) &= dfs(i + 1) + (dfs(i + 1) - dfs(i + \textit{maxPts} + 1)) / \textit{maxPts} \end{aligned}

如果 $i=k-1$ ，有：

\begin{aligned} dfs(i) &= dfs(k - 1) &= dfs(k) + dfs(k + 1) + \cdots + dfs(k + \textit{maxPts} - 1) / \textit{maxPts} & (3) \end{aligned}

我们假设有 $i$ 个数不超过 $n$ ，那么 $k+i-1 \leq n$ ，又因为 $i\leq \textit{maxPts}$ ，所以 $i \leq \min(n-k+1, \textit{maxPts})$ ，因此等式 $(3)$ 可以写成：

\begin{aligned} dfs(k-1) &= \min(n-k+1, \textit{maxPts}) / \textit{maxPts} \end{aligned}

综上所述，有以下状态转移方程：

\begin{aligned} dfs(i) &= \begin{cases} 1, & i \geq k, i \leq n \\ 0, & i \geq k, i \gt n \\ \min(n-k+1, \textit{maxPts}) / \textit{maxPts}, & i = k - 1 \\ dfs(i + 1) + (dfs(i + 1) - dfs(i + \textit{maxPts} + 1)) / \textit{maxPts}, & i < k - 1 \end{cases} \end{aligned}

时间复杂度 $O(k + \textit{maxPts})$ ，空间复杂度 $O(k + \textit{maxPts})$ 。其中 $k$ 为最大分数。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        @cache
        def dfs(i: int) -> float:
            if i >= k:
                return int(i <= n)
            if i == k - 1:
                return min(n - k + 1, maxPts) / maxPts
            return dfs(i + 1) + (dfs(i + 1) - dfs(i + maxPts + 1)) / maxPts

        return dfs(0)

speed

复杂度分析

指标	值
时间	complexity is O(n) using sliding window accumulation for dp, and space complexity is O(n) to store the DP array. Without sliding window optimization, naive DP would be O(n*maxPts).
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate defines dp[x] clearly and explains why each state depends on previous maxPts states.
question_mark
Candidate optimizes naive DP using a sliding window to reduce time complexity.
question_mark
Candidate correctly handles edge cases like k = 0 or n < k without overcounting probabilities.

warning

常见陷阱

外企场景

error
Attempting naive summation of all prior states for each dp[x], leading to TLE.
error
Forgetting to cap the probability sum at n, causing overestimation.
error
Not accounting for k = 0, which should immediately return 1.0 probability.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Change maxPts to a non-uniform probability distribution for each draw, requiring weighted DP.
arrow_right_alt
Compute expected value instead of probability, altering the DP recurrence slightly.
arrow_right_alt
Consider multiple players drawing sequentially, updating DP to track joint probabilities.

help

常见问题

外企场景

继续练习

#808 分汤 #1227 飞机座位分配概率 #1467 两个盒子中球的颜色数相同的概率