SGU 495 Kids and Prizes：機率 DP 與期望值公式推導

SGU 495 Kids and Prizes：機率 DP 與期望值公式推導

題目大意

有 n 個盒子，其中 1 個藏有獎品。m 個人依序抽取：每人隨機選一個盒子，若抽中獎品則取出獎品並將盒子放回；若未抽中則直接放回。求 m 個人抽結束後，總共抽中獎品數的期望值。

方法一：機率動態規劃

定義 dp[i] 為第 i 個人抽中獎品的機率。邊界：dp[1] = 1（第一人必中）。

狀態轉移：第 i 人抽中獎品有兩種互斥情況：

1. 第 i-1 人未抽中（機率 1-dp[i-1]），獎品仍在 n 個盒子中，本人抽中機率 1/n，但實際上等同於 dp[i-1]？經推導：
2. 第 i-1 人已抽中（機率 dp[i-1]），獎品被取走，盒子變空，本人抽中機率為 0？實際上獎品會被取出，但盒子放回，所以下一輪獎品數減 1，總盒子數仍為 n。因此第 i 人抽中機率 = (n-1)/n * (1/(n-1))? 經仔細推導：

正確轉移方程：

dp[i] = dp[i-1] * (1 - 1.0/n) + (1 - dp[i-1]) * (1.0/n)
// 解釋：
// 若前人中獎(機率 dp[i-1])，剩 n-1 個獎品在 n 盒中，本人中獎率 (n-1)/n = 1 - 1/n
// 若前人未中(機率 1-dp[i-1])，仍有 n 個獎品，本人中獎率 1/n

期望值 = Σ dp[i] (i=1..m)。

方法二：數學期望公式（最優雅）

從獎品視角：每個獎品在 m 輪中不被選中的機率為 ((n-1)/n)^m。
n 個獎品都不被選中的期望數 = n * ((n-1)/n)^m。
因此被選中的期望數 = n - n * ((n-1)/n)^m。

完整代碼（方法二）

#include 
#include 
using namespace std;

int main() {
    int n, m;
    while (~scanf("%d%d", &n, &m)) {
        double ans = n;
        double tmp = 1.0;
        for (int i = 1; i <= m; ++i)
            tmp *= (n - 1.0) / n;
        ans -= n * tmp;
        printf("%.10lf\n", ans);
    }
    return 0;
}

心得總結

• DP 思路雖可行，但需正確建模「獎品被取走後盒子狀態」。
• 數學期望公式利用獨立事件性質，將複雜的序列依賴轉化為簡單的冪運算，體現「換個角度思考」的威力。
• 題目中 n 可能小於 m，但公式自動處理：當獎品被取完後，後續項為 0，不影響結果。