数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++ 抛掷奇异硬币
假设我们有一些硬币。抛掷第 i 个硬币时，正面朝上的概率为 prob[i]。如果我们恰好抛掷每一个硬币一次，我们需要计算正面朝上硬币数量等于目标值 target 的概率。例如，如果 prob 数组为 [0.5,0.5,0.5,0.5,0.5]，target 为 0，则输出为 0.03125。
为了解决这个问题，我们将遵循以下步骤：
- n := prob 数组的大小
- 创建一个大小为 n x (target + 5) 的二维数组
- 设置 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 到 min(i + 1, target)
- dp[i, j] := (1 – prob[i]) * dp[i – 1, j] + prob[i]*dp[i – 1, j - 1]
- 返回 dp[n – 1, target]
让我们来看下面的实现，以便更好地理解：
示例
#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
更新于：2020年4月30日
591 次浏览
广告