Facing Heads Probabilties of Tossing Strange Coins using Dynamic
- 时间:2020-09-18 17:01:02
- 分类:网络文摘
- 阅读:79 次
You have some coins. The i-th coin has a probability prob[i] of facing heads when tossed. Return the probability that the number of coins facing heads equals target if you toss every coin exactly once.
Example 1:
Input: prob = [0.4], target = 1
Output: 0.40000Example 2:
Input: prob = [0.5,0.5,0.5,0.5,0.5], target = 0
Output: 0.03125Constraints:
1 <= prob.length <= 1000
0 <= prob[i] <= 1
0 <= target <= prob.length
Answers will be accepted as correct if they are within 10^-5 of the correct answer.Hints:
What about solving the problem with DP?
Use DP with two states dp[pos][cnt], where pos represents the pos-th coin and cnt is the number of heads seen so far.
You can do the transitions with a little bit math.
For the base case, when pos == n return (cnt == target) to filter out the invalid scenarios.
Depth First Search Algorithm to Calculate the Toss Probabilities
Each coin is tossed exactly once, and the probability of overall heads facing up stays the same regardless the order of the coins to toss. We can start at the first coin, imaging a binary tree where the root is the first coin, then the left tree is when the head faces up and the right tree when the head faces down. Therefore, the tree can be depth first search or breadth first search.
When we toss the last coin, we can check if the number of the heads up equal to the target, if yes, we accumulates the probability. We can speed up DFS by abandoning the branches where when we have tossed more than heads we wanted or the current probability is zero.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | class Solution { public: double probabilityOfHeads(vector<double>& prob, int target) { dfs(prob, 0, target, 1); return total; } private: double total = 0; void dfs(vector<double>& prob, int index, int target, double cur) { if (target < 0) { return; } if (cur == 0) { return; } if (index >= prob.size()) { if (target == 0) { total += cur; } return; } dfs(prob, index + 1, target, cur * (1 - prob[index])); dfs(prob, index + 1, target - 1, cur * prob[index]); } }; |
class Solution { public: double probabilityOfHeads(vector<double>& prob, int target) { dfs(prob, 0, target, 1); return total; } private: double total = 0; void dfs(vector<double>& prob, int index, int target, double cur) { if (target < 0) { return; } if (cur == 0) { return; } if (index >= prob.size()) { if (target == 0) { total += cur; } return; } dfs(prob, index + 1, target, cur * (1 - prob[index])); dfs(prob, index + 1, target - 1, cur * prob[index]); } };
However, as the depth of the binary tree can go very deep, the performance may be hit greatly. The complexity is O(2^N) where N is the number of the coins – we may need to traverse all branches/nodes of the binary search tree.
The DFS is the TOP-Down search as we are search from the root (first coin) onwards.
Using Dynamic Programming Algorithm to Compute the Probabilties of Tossing a Coin
We can perform the calculations bottom-up using Dynamic Programming Algorithm. Let dp[i][j] represent the probability of getting j coins facing up after tossing the i-th coin. Therefore, we know that the probability of dp[i][j] can be accumulated from two parts: dp[i – 1][j] and dp[i – 1][j – 1].
For dp[i – 1][j], we have enough j coins facing up, thus for i-th coin, it has to face down – which is 1 – prob[i]. Similarly, for dp[i – 1][j – 1], we have to toss a facing-up coin, which is prob[i]
The initial values:
1 2 | dp[0][1] = prob[0]; dp[0][1] = 1 - prob[0]; |
dp[0][1] = prob[0]; dp[0][1] = 1 - prob[0];
And we have to fill the dp[i][0] values which can be easily pre-computed:
1 | dp[i][0] = dp[i - 1][0] * (1 - prob[i]); |
dp[i][0] = dp[i - 1][0] * (1 - prob[i]);
The following C++ implements the DP:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | class Solution { public: double probabilityOfHeads(vector<double>& prob, int target) { if (prob.empty()) return 0; vector<vector<double>> dp(prob.size(), vector<double>(prob.size() + 1, 0)); dp[0][1] = prob[0]; dp[0][0] = 1 - prob[0]; for (int i = 1; i < prob.size(); ++ i) { dp[i][0] = dp[i - 1][0] * (1 - prob[i]); for (int j = 1; j <= target; ++ j) { dp[i][j] = dp[i - 1][j] * (1 - prob[i]) + dp[i - 1][j - 1] * prob[i]; } } return dp[prob.size() - 1][target]; } }; |
class Solution { public: double probabilityOfHeads(vector<double>& prob, int target) { if (prob.empty()) return 0; vector<vector<double>> dp(prob.size(), vector<double>(prob.size() + 1, 0)); dp[0][1] = prob[0]; dp[0][0] = 1 - prob[0]; for (int i = 1; i < prob.size(); ++ i) { dp[i][0] = dp[i - 1][0] * (1 - prob[i]); for (int j = 1; j <= target; ++ j) { dp[i][j] = dp[i - 1][j] * (1 - prob[i]) + dp[i - 1][j - 1] * prob[i]; } } return dp[prob.size() - 1][target]; } };
The space requirement is O(N^2) and the time complexity is also O(N^2) where N is the number of the coins.
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:文化艺术节 关于报刊亭的数学题 数学题:当甲车到达时,乙车距离工地还有24千米 数学题:光华小学中、高年级共有学生600名 数学题:求大阴影部分的面积 数学题:如何只用这2个水壶从池塘里取得3升的水 关于可能性的数学题 数学题:ABCD乘9等于DCBA,问ABCD各是数字几 数学题:乘积末尾有几个0 求解答:加工一批服装,每天加工300套,16天可以完成
- 评论列表
-
- 添加评论