837. New 21 Game

Ackerman

2025/08/19 更新2025/08/19 發佈閱讀 7 分鐘

[Medium] 解法 : DP + sliding window

題意 :

給定 n、k、maxPts

起始分數為 0。
當分數小於 k 時，會隨機抽一個介於 1 到 maxPts 的整數點數，每次抽牌機率相同且獨立。
當分數達到或超過 k 時停止抽牌。

回傳最終分數 不超過 n 的機率。

解題思路 :

給定k的情況下，在 k-1時抽到maxPts可讓拿到分數最大，最大值為k+maxPts-1

因此在停止抽牌時，可以拿到的分數如下 :

[k, k+1, ..., k+maxPts-1]

可以歸類出 3 種例外狀況

k == 0 : 不能抽牌，分數為0，顯然 <= n
n >= (k + maxPts - 1) : 結束抽牌時，分數最大為(k + maxPts - 1)，永遠 <= n
n < k : 結束抽牌時，分數最小為 k，分數不可能 <= n

// 特殊情況處理
if (k == 0) return 1.0;               // 不需要抽牌就結束
if (n < k) return 0.0;                // 沒有機會到達目標
if (n >= k + maxPts - 1) return 1.0;  // 範圍足夠，必定成功

剩下情況以DP方式逐步推得解。會有一陣列p，p[i]代表的意思可以抽牌的情況下，抽牌後可讓點數為 i 的機率。

從 [1, maxPts] 抽取任一張牌的機率皆為 1/maxPts，要讓點數為 i 的機率可以由以下來推得。(假設 maxPts = 5)

// i=1
p(1) = 1/5*p(0)    (抽了分數為1的牌)
// i=2
p(2) = 1/5*p(1) + 1/5*p(0) (抽了分數為1的牌) + (抽了分數為2的牌)
// i=3
p(3) = 1/5*p(2) + 1/5*p(1) + 1/5*p(0)
// i=4
p(4) = 1/5*p(3) + 1/5*p(2) + 1/5*p(1) + 1/5*p(0)
// i=5
p(5) = 1/5*p(4) + 1/5*p(3) + 1/5*p(2) + 1/5*p(1) + 1/5*p(0)
// i=6
p(6) = 1/5*p(5) + 1/5*p(4) + 1/5*p(3) + 1/5*p(2) + 1/5*p(1)

可觀察到規律， p[i]的值可由前面求出的機率值推出 (p[i-1]、p[i-2]...等)

因此可用 sliding window，並以 windowSum紀錄先前求出機率的和

// i=1
p(1) = 1/5*windowSum (windowSum = p(0))
// i=2
p(2) = 1/5*windowSum (windowSum = p(0)+p(1))
// i=3
p(3) = 1/5*windowSum (windowSum = p(0)+p(1)+p(2))
// i=4
p(4) = 1/5*windowSum (windowSum = p(0)+p(1)+p(2)+p(3))
// i=5
p(5) = 1/5*windowSum (windowSum = p(0)+p(1)+p(2)+p(3)+p(4))
// i=6
p(6) = 1/5*windowSum (windowSum = p(1)+p(2)+p(3)+p(4)+p(5))

每次更新 p[i]時都會將 p[i-1]加進windowSum，但如果(i-1) >= k代表累積分數 (i-1)已經達到停止抽牌的門檻，因此沒辦法進行抽牌使分數變成 i，所以在這情況下 p[i-1]不會被加進windowSum

在更新windowSum有以下要注意：

當 i ≤ maxPts，windowSum 可直接累加先前的 p 值，因可累加範圍還未滿。
當 i > maxPts，視窗長度已滿，要將整個視窗 shift 一格

shift 一格時會需要剃除舊有的值，因此會用 l變數作為 window 最左邊下次需要被剃除的機率索引。

最後p[k]+p[k+1]+...p[n]即是答案

class Solution {
public:
    double new21Game(int n, int k, int maxPts) {
        // 特殊情況處理
        if (k == 0) return 1.0;               // 不需要抽牌就結束
        if (n < k) return 0.0;                // 沒有機會到達目標
        if (n >= k + maxPts - 1) return 1.0;  // 範圍足夠，必定成功

        vector<double> p(n+1, 0); // p[i] : 可以抽牌的情況下，抽牌後可讓點數為 i 的機率
        p[0] = 1;
        double windowSum = 0;
        int l = 0;

        for(int i=1 ; i<=n ; ++i){
            // (i-1) < k 時代表可以執行抽牌的動作
            if(i-1 < k)
                windowSum += p[i-1];
            // 執行 shift 動作
            if(i > maxPts){
                windowSum -= p[l];
                ++l;
            }
            p[i] = windowSum / maxPts;
        }
        return accumulate(p.begin() + k, p.end(), 0.0);
    } 
};