สมมุติว่าเรามีเหรียญ เหรียญที่ i มีโอกาสเสี่ยงที่จะโดนหัวเมื่อถูกโยน เราต้องแสดงความน่าจะเป็นที่จำนวนของเหรียญที่เผชิญหน้าเท่ากับเป้าหมาย ถ้าคุณโยนทุกเหรียญเพียงครั้งเดียว ดังนั้นหากอาร์เรย์ของผลลัพธ์เป็น [0.5,0.5,0.5,0.5,0.5] และเป้าหมายเป็น 0 ผลลัพธ์จะเป็น 0.03125
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- n :=ขนาดของโพรบอาร์เรย์
- สร้างอาร์เรย์ 2 มิติขนาด n x (เป้าหมาย + 5)
- set 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 ถึงขั้นต่ำของ 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
