LeetCode 837.新 21 點：動態規劃+滑動窗口

【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 <= 10⁴
1 <= maxPts <= 10⁴

解題方法：動態規劃

這道題有點“反向dp”。令 $d p [i]$ 表示當愛麗絲獲得 $i$ 分時，最終獲勝的概率。

其中“獲勝”是指最終分數 $≥k\geq k$ 且 $≤n\leq n$ ，那么初始狀態0分時 $d p [0]$ 即位所求。

一旦愛麗絲分數 $≥k\geq k$ 她就立即停止抽牌，由于最后一張牌的分數范圍是 $1$ 到 $ma x Pt s$ ，所以最終分數的可能范圍是從 $k$ 到 $k + ma x Pt s ? 1$ ，可得dp數組的初始狀態：

$dp[i]={1if?i≤n0else?,k≤i<k+maxPtsdp[i]=\begin{cases} 1 \text{ if } i\leq n \\ 0 \text{ else } \end{cases}\ \ \ ,\ k\leq i\lt k+maxPts$

那么在她手中的分數還未達到游戲終止時（假設當前為 $i$ 分），由于再抽一張牌可以等概率達到 $\cdots, i+maxPts$ ，所以可得狀態轉移方程：

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

由于每次計算 $dp[i+1]+dp[i+2]+?+dp[i+maxPts]dp[i+1]+dp[i+2]+\dots+dp[i+maxPts]$ 太過于機械和重復，所以可以參考“滑動窗口”的思想，使用一個變量 $s$ 記錄“窗口”中 $ma x Pt s$ 個元素的和，并隨著窗口的前移不斷更新 $s$ 即可。

時間復雜度 $O (k + ma x Pt s)$
空間復雜度 $O (k + ma x Pt s)$

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和我的個人博客，原創不易，轉載經作者同意后請附上原文鏈接哦~

千篇源碼題解已開源

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/diannao/96088.shtml
繁體地址，請注明出處：http://hk.pswp.cn/diannao/96088.shtml
英文地址，請注明出處：http://en.pswp.cn/diannao/96088.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！