ধরুন আমাদের কিছু কয়েন আছে। i-th মুদ্রায় ছুঁড়ে ফেলার সময় মাথার মুখোমুখি হওয়ার সম্ভাবনা রয়েছে। আমাদের সম্ভাবনা দেখাতে হবে যে মাথার দিকে থাকা কয়েনের সংখ্যা লক্ষ্যের সমান হবে যদি আপনি প্রতিটি কয়েন ঠিক একবার টস করেন। সুতরাং যদি প্রোব অ্যারে [0.5,0.5,0.5,0.5,0.5] এর মত হয় এবং লক্ষ্য 0 হয়, তাহলে আউটপুট হবে 0.03125।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- n :=প্রোব অ্যারের আকার
- ন x (লক্ষ্য + 5) আকারের একটি 2d অ্যারে তৈরি করুন
- dp[0,0] =1 – prob[0] এবং dp[0,1] :=সমস্যা[0] সেট করুন
- আমি 1 থেকে n – 1
- পরিসরে
- dp[i, 0] :=(1 – prob[i]) * dp[i – 1, 0]
- j এর জন্য রেঞ্জ 1 থেকে সর্বনিম্ন i + 1 এবং লক্ষ্য
- dp[i, j] :=(1 – prob[i]) * dp[i – 1, j] + prob[i]*dp[i – 1, j - 1]
- রিটার্ন dp[n – 1, টার্গেট]
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#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
