동전이 있다고 가정해 봅시다. i번째 동전은 던졌을 때 앞면이 나올 확률[i]이 있습니다. 모든 동전을 정확히 한 번 던진다면 앞면을 향하는 동전의 수가 목표와 같을 확률을 보여줘야 합니다. 따라서 prob 배열이 [0.5,0.5,0.5,0.5,0.5]이고 target이 0이면 출력은 0.03125가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- n :=프로브 배열의 크기
- 크기 n x(타겟 + 5)의 2차원 배열 하나 생성
- dp[0,0] =1 – prob[0] 및 dp[0,1]:=prob[0] 설정
- 1 ~ n – 1 범위의 i에 대해
- dp[i, 0] :=(1 – 확률[i]) * dp[i – 1, 0]
- i 범위 1에서 최소 i + 1 및 target
- 에 있는 j의 경우
- 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