Giả sử chúng ta có một số đồng xu. Đồng xu thứ i có xác suất [i] đối mặt với các đầu khi tung. Chúng ta phải chỉ ra xác suất sao cho số đồng xu có mặt ngửa bằng với mục tiêu nếu bạn tung mỗi đồng xu chính xác một lần. Vì vậy, nếu mảng khảo sát giống như [0,5,0.5,0.5,0.5,0.5] và mục tiêu là 0, thì đầu ra sẽ là 0,03125.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- n:=kích thước của mảng prob
- tạo một mảng 2d có kích thước n x (target + 5)
- đặt dp [0,0] =1 - prob [0] và dp [0,1]:=prob [0]
- cho tôi trong phạm vi từ 1 đến n - 1
- dp [i, 0]:=(1 - prob [i]) * dp [i - 1, 0]
- cho j trong phạm vi từ 1 đến tối thiểu là i + 1 và mục tiêu
- dp [i, j]:=(1 - prob [i]) * dp [i - 1, j] + prob [i] * dp [i - 1, j - 1]
- trả về dp [n - 1, target]
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#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));
} Đầu vào
[0.5,0.5,0.5,0.5,0.5] 0
Đầu ra
0.03125