[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);
}
};
Extra :
題目有點抽象，看了 contest rating 難度為 2350 分。看懂機率求得的過程花了不少時間@@
