假设我们有一些硬币。第i个硬币具有概率概率扔当磁头面对的[i]中。我们必须表明，面临头硬币的数目等于目标，如果你抛硬币每一次准确的概率。因此，如果概率数组像[0.5,0.5,0.5,0.5,0.5]并且目标为0，那么输出将为0.03125。
为了解决这个问题，我们将遵循以下步骤-
-
n：=概率数组的大小
-
创建大小为nx的一个2D阵列（靶+ 5）
-
组DP [0,0] = 1 - 概率[0]和DP [0,1]：=概率[0]
-
当我在1到n – 1的范围内时
-
dp [i，j]：=（1-prob [i]）* dp [i – 1，j] + prob [i] * dp [i – 1，j-1]
-
dp [i，0]：=（1 –概率[i]）* dp [i – 1，0]
-
对于范围在1到i + 1最小值之间的j并目标
-
返回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
