友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
837. 新 21 点
爱丽丝参与一个大致基于纸牌游戏 “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 <= 104 -
1 <= maxPts <= 104
思路分析
定长滑动窗口的解法还需要再思考一下，不是很懂！
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-07-28 21:55:38
*/
public double new21Game(int n, int k, int maxPts) {
double[] f = new double[n + 1];
double s = 0;
for (int i = n; i >= 0; i--) {
f[i] = i >= k ? 1 : s / maxPts;
// 当前循环计算的是 f[i+1] + ... + f[i+maxPts]
// 下个循环计算的是 f[i] + ... + f[i+maxPts-1]，多了 f[i]，少了 f[i+maxPts]
s += f[i];
if (i + maxPts <= n) {
s -= f[i + maxPts];
}
}
return f[0];
}
参考资料
-
837. 新 21 点 - 滑动窗口优化 DP，简洁写法 — 前半段思路没问题，后面转移方程懵逼了！