मान लीजिए हमारे पास कुछ सिक्के हैं। i-वें सिक्के के उछालने पर हेड आने की संभावना prob[i] है। हमें वह संभावना दिखानी है कि यदि आप प्रत्येक सिक्के को ठीक एक बार उछालते हैं तो हेड वाले सिक्कों की संख्या target के बराबर होगी। उदाहरण के लिए, यदि prob सरणी [0.5,0.5,0.5,0.5,0.5] है और target 0 है, तो आउटपुट 0.03125 होगा।
हल करने के चरण
- n := prob सरणी का आकार
- n x (target + 5) आकार का एक 2D सरणी बनाएं
- dp[0][0] = 1 - prob[0] और dp[0][1] := prob[0] सेट करें
- 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]
- dp[n-1][target] वापस करें
उदाहरण
#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+5)); dp[0][0] = 1- prob[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]; } }; main(){ vector<double> v = {0.5,0.5,0.5,0.5,0.5}; Solution ob; cout << (ob.probabilityOfHeads(v, 0)); }इनपुट
[0.5,0.5,0.5,0.5,0.5] 0
आउटपुट
0.03125