Toss Strange Coins ใน C++: ความน่าจะเป็นจำนวนหัวเท่ากับ Target

โจทย์

มีเหรียญ n อัน เหรียญที่ i มีโอกาส prob[i] ที่จะออกหัว หาโอกาสที่จำนวนหัวเท่ากับ target ทุกอย่างเมื่อทอยครบ 1 รอบ

ตัวอย่าง: prob = [0.5,0.5,0.5,0.5,0.5], target = 0 → 0.03125 (0.5^5)

แนวคิด: Dynamic Programming

dp[i][j] = โอกาสที่ทอยเหรียญแรก i+1 อัน ได้หัว j ครั้ง

สัญลักษณ์: dp[i][j] = (1-prob[i])*dp[i-1][j] + prob[i]*dp[i-1][j-1]

ขั้นตอน

1. n = prob.size(), สร้าง dp[n][target+1] เริ่มต้น 0
2. dp[0][0] = 1 - prob[0], dp[0][1] = prob[0]
3. ลูป i = 1 ถึง n-1:
   • dp[i][0] = (1-prob[i]) * dp[i-1][0]
   • ลูป j = 1 ถึง min(i+1, target):
     • dp[i][j] = (1-prob[i])*dp[i-1][j] + prob[i]*dp[i-1][j-1]
4. คืน dp[n-1][target]

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    double probabilityOfHeads(vector<double>& prob, int target) {
        int n = prob.size();
        vector<vector<double>> dp(n, vector<double>(target + 1, 0.0));
        
        dp[0][0] = 1 - prob[0];
        if (target >= 1) dp[0][1] = prob[0];
        
        for (int i = 1; i < n; i++) {
            dp[i][0] = (1 - prob[i]) * dp[i-1][0];
            for (int j = 1; j <= min(i+1, target); j++) {
                dp[i][j] = (1 - prob[i]) * dp[i-1][j] + prob[i] * dp[i-1][j-1];
            }
        }
        return dp[n-1][target];
    }
};

int main() {
    Solution ob;
    vector<double> v = {0.5, 0.5, 0.5, 0.5, 0.5};
    cout << fixed << setprecision(5) << ob.probabilityOfHeads(v, 0); // 0.03125
    return 0;
}

อินพุต / เอาต์พุต

Input: [0.5,0.5,0.5,0.5,0.5] 0

Output: 0.03125

ความซับซ้อน

• Time: O(n × target)
• Space: O(n × target) → สามารถลดเหลือ O(target) ด้วย 1D DP ได้