প্রতিটি সিক্কার হেড আসার প্রোবাবিলিটি prob[i] দেওয়া। সব সিক্কা একবার করে উল্টালে ঠিক target সংখ্যক হেড আসার প্রোবাবিলিটি বের করতে হবে।
উদাহরণ: prob = [0.5,0.5,0.5,0.5,0.5], target = 0 → আউটপুট 0.03125।
সমাধানের ধাপসমূহ
- DP টেবিল
dp[i][j]= প্রথম i টি সিক্কা থেকে j টি হেড পাওয়ার প্রোবাবিলিটি। dp[0][0] = 1 - prob[0],dp[0][1] = prob[0]।- ট্রানজিশন:
dp[i][j] = (1-prob[i])*dp[i-1][j] + prob[i]*dp[i-1][j-1]। - উত্তর:
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));
dp[0][0] = 1 - prob[0];
if (target > 0) 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() {
vector<double> v = {0.5,0.5,0.5,0.5,0.5};
Solution ob;
cout << fixed << setprecision(5) << ob.probabilityOfHeads(v, 0);
}
ইনপুট
[0.5,0.5,0.5,0.5,0.5] 0
আউটপুট
0.03125
