【LetMeFly】837.新 21 点：动态规划+滑动窗口

力扣题目链接：https://leetcode.cn/problems/new-21-game/

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

解题方法：动态规划

这道题有点“反向dp”。令$dp[i]$表示当爱丽丝获得$i$分时，最终获胜的概率。

其中“获胜”是指最终分数$\ge k$且$\le n$，那么初始状态0分时$dp[0]$即位所求。

一旦爱丽丝分数$\ge k$她就立即停止抽牌，由于最后一张牌的分数范围是$1$到$maxPts$，所以最终分数的可能范围是从$k$到$k+maxPts-1$，可得dp数组的初始状态：

$$dp[i]=\{\begin{array}{l}1\text{ if }i\le n\\ 0\text{ else }\end{array},k\le i<k+maxPts$$

那么在她手中的分数还未达到游戏终止时（假设当前为$i$分），由于再抽一张牌可以等概率达到$i+1,i+2,\cdots ,i+maxPts$，所以可得状态转移方程：

$$dp[i]=\frac{dp[i+1]+dp[i+2]+\cdots +dp[i+maxPts]}{maxPts}$$

由于每次计算$dp[i+1]+dp[i+2]+\cdots +dp[i+maxPts]$太过于机械和重复，所以可以参考“滑动窗口”的思想，使用一个变量$s$记录“窗口”中$maxPts$个元素的和，并随着窗口的前移不断更新$s$即可。

• 时间复杂度$O(k+maxPts)$
• 空间复杂度$O(k+maxPts)$

AC代码

C++

/** @Author: LetMeFly* @Date: 2025-08-17 19:33:11* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-08-17 19:38:09*/
class Solution {
public:double new21Game(int n, int k, int maxPts) {vector<double> dp(k + maxPts);double s = 0;for (int i = k; i < k + maxPts; i++) {dp[i] = i <= n;s += dp[i];}for (int i = k - 1; i >= 0; i--) {dp[i] = s / maxPts;s = s - dp[i + maxPts] + dp[i];}return dp[0];}
};

Python

'''
Author: LetMeFly
Date: 2025-08-17 19:33:11
LastEditors: LetMeFly.xyz
LastEditTime: 2025-08-17 19:40:07
'''
class Solution:def new21Game(self, n: int, k: int, maxPts: int) -> float:dp = [0.] * (k + maxPts)s = 0.for i in range(k, k + maxPts):dp[i] = 1. if i <= n else 0.s += dp[i]for i in range(k - 1, -1, -1):dp[i] = s / maxPtss = s + dp[i] - dp[i + maxPts]return dp[0]

Java

/** @Author: LetMeFly* @Date: 2025-08-17 19:33:11* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-08-17 19:43:15*/
class Solution {public double new21Game(int n, int k, int maxPts) {double[] dp = new double[k + maxPts];double s = 0;for (int i = k; i < k + maxPts; i++) {dp[i] = i <= n ? 1. : 0.;s += dp[i];}for (int i = k - 1; i >= 0; i--) {dp[i] = s / maxPts;s = s + dp[i] - dp[i + maxPts];}return dp[0];}
}

Go

/** @Author: LetMeFly* @Date: 2025-08-17 19:33:11* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-08-17 22:20:30*/
package mainfunc new21Game(n int, k int, maxPts int) float64 {dp := make([]float64, k + maxPts)s := 0.for i := k; i < k + maxPts; i++ {if i <= n {dp[i] = 1.} else {dp[i] = 0.}s += dp[i]  // 别忘了}for i := k - 1; i >= 0; i-- {dp[i] = s / float64(maxPts)s = s + dp[i] - dp[i + maxPts]}return dp[0]
}

Rust

/** @Author: LetMeFly* @Date: 2025-08-17 19:33:11* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-08-17 22:31:00*/
impl Solution {pub fn new21_game(n: i32, k: i32, max_pts: i32) -> f64 {let k: usize = k as usize;let max_pts: usize = max_pts as usize;let n: usize = n as usize;let mut dp: Vec<f64> = vec![0 as f64; k + max_pts];let mut s: f64 = 0.;for i in k..(k+max_pts) {if i <= n {dp[i] = 1.;} else {dp[i] = 0.;}s += dp[i];}for i in (0..k).rev() {dp[i] = s / max_pts as f64;s = s + dp[i] - dp[i + max_pts];}dp[0]}
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源