Title

愛麗絲參與一個大致基于紙牌游戲 “21點” 規則的游戲，描述如下：

愛麗絲以 0 分開始，并在她的得分少于 K 分時抽取數字。 抽取時，她從 [1, W] 的范圍中隨機獲得一個整數作為分數進行累計，其中 W 是整數。 每次抽取都是獨立的，其結果具有相同的概率。

當愛麗絲獲得不少于 K 分時，她就停止抽取數字。 愛麗絲的分數不超過 N 的概率是多少？

示例 1：

輸入：N = 10, K = 1, W = 10
輸出：1.00000
說明：愛麗絲得到一張卡，然后停止。

示例 2：

輸入：N = 6, K = 1, W = 10
輸出：0.60000
說明：愛麗絲得到一張卡，然后停止。
在 W = 10 的 6 種可能下，她的得分不超過 N = 6 分。

示例 3：

輸入：N = 21, K = 17, W = 10
輸出：0.73278

提示：

0 <= K <= N <= 10000
1 <= W <= 10000
如果答案與正確答案的誤差不超過 10^-5，則該答案將被視為正確答案通過。
此問題的判斷限制時間已經減少。

Solve

動態規劃

下一局獲勝的概率和當前的得分有關，令dp[x]表示從得分x的情況開始游戲并且獲勝的概率，目標是求dp[0]的值。

根據規則，當分數不小于K時游戲結束，而游戲結束時，如果分數不超過N則獲勝，如果分數超過N則失敗，因此當K<=x<=min(N,K+W-1)時有dp[x]=1，當x>min(N,K+W-1)時有dp[x]=0。

min(N,K+W-1)是什么鬼？首先，只有當分數不超過N時才算獲勝，其次，可以達到的最大分數為K+W-1，即在最后一次抽取數字之前的分數為K-1，并在本輪抽到了W。

當0<=x<=K時，在范圍[1,W]內隨機抽取一個整數，且每個整數被抽取到的概率相等，因此可以得到如下狀態轉移方程：
$$dp[x]=\frac{dp[x+1]+dp[x+2]+...+dp[x+W]}{W}$$
對dp的相鄰項計算差分：
$$dp[x]?dp[x+1]=\frac{dp[x+1]?dp[x+W+1]}{W}$$
此時0<=x<K-1，可以得到新的狀態轉移方程：
$$dp[x]=dp[x+1]?\frac{dp[x+1]?dp[x+W+1]}{W}$$
注意到x的取值范圍，當x=K-1時不適用，所以：
$$dp[K?1]=\frac{dp[K]+dp[K+1]+...+dp[K+W?1]}{W}$$
注意到只有當K<=x<=min(N,K+W?1)時才有 dp[x]=1，因此：
$$dp[K?1]=\frac{min(N,K+W?1)?K+1}{W}=\frac{min(N?K+1,W)}{W}$$
對于 dp[K-2] 到 dp[0] 的值，則可通過新的狀態轉移方程得到。

**復雜度分析

時間復雜度：O(min(N,K+W))。即需要計算的 dp 值的數量min(N,K+W?1)。

空間復雜度：O(K+W)。創建了一個長度為 K+W+1 的數組 dp。

Code

class Solution:def new21Game(self, N: int, K: int, W: int) -> float:if K == 0:return 1.0dp = [0.0] * (K + W + 1)for i in range(K, min(N, K + W - 1) + 1):dp[i] = 1.0dp[K - 1] = float(min(N - K + 1, W) / W)for i in range(K - 2, -1, -1):dp[i] = dp[i + 1] - (dp[i + W + 1] - dp[i + 1]) / Wreturn dp[0]

總結

以上是生活随笔為你收集整理的837. New 21 Game的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。