抛奇怪硬币在C ++中
假设我们有一些硬币。第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