MediumRating 2350
837. New 21 Game
mathdynamic-programmingsliding-windowprobability-and-statistics
解題說明
New 21 Game
題目描述:Alice 玩一個抽牌遊戲。她從 0 分開始,每次隨機抽取 1 到 maxPts 中的一個整數加到分數上。當分數達到或超過 k 時停止抽牌。求她最終分數不超過 n 的機率。
解題思路:定義 dp[x] 為分數恰好為 x 的機率。轉移方程:
- 對於
x < k:dp[x] = (dp[x-1] + dp[x-2] + ... + dp[x-maxPts]) / maxPts - 對於
x >= k:不再抽牌,機率由之前的狀態累積。
直接計算每個 dp[x] 需要 O(maxPts) 時間,但可以用滑動視窗(前綴和)優化。維護一個視窗和 windowSum:
windowSum代表dp[x-maxPts] + dp[x-maxPts+1] + ... + dp[x-1]。dp[x] = windowSum / maxPts。- 更新視窗時加入
dp[x](僅當x < k時,因為 x >= k 後不再抽牌)。 - 移除超出視窗的
dp[x-maxPts]。
最終答案為 dp[k] + dp[k+1] + ... + dp[n]。
C++ 解法
複雜度分析
時間複雜度:O(n) — 單次遍歷計算 dp 陣列,滑動視窗使每步更新為 O(1)。
空間複雜度:O(n) — dp 陣列大小為 n+1。
虛擬碼
1. If k == 0 or n >= k + maxPts - 1, return 1.0 2. dp[0] = 1.0, windowSum = 1.0 3. For x from 1 to n: a. dp[x] = windowSum / maxPts b. If x < k: windowSum += dp[x] (still in game) c. If x >= maxPts: windowSum -= dp[x - maxPts] (slide window) 4. Return sum of dp[k..n]
其他解法
直接 DP(無滑動視窗):每個 dp[x] 都從前 maxPts 個狀態相加。時間 O(n * maxPts),空間 O(n)。在 maxPts 很大時會超時,但邏輯更容易理解。
逆向思考:計算分數超過 n 的機率,用 1 減去。但轉移方程相同,沒有實質優化。
延伸思考
- 為什麼當
n >= k + maxPts - 1時答案必定為 1.0? - 滑動視窗和前綴和在此問題中的等價性是什麼?
- 如果每次抽取的數字不是均勻分佈,而是有不同的機率,該如何修改?