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.40000
Example 2:
Input: prob = [0.5,0.5,0.5,0.5,0.5], target = 0 Output: 0.03125
Constraints:
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.
Solution: DP
dp[i][j] := prob of j coins face up after tossing first i coins.
dp[i][j] = dp[i-1][j] * (1 – p[i]) + dp[i-1][j-1] * p[i]
Time complexity: O(n^2)
Space complexity: O(n^2) -> O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 |
// Author: Huahua class Solution { public: double probabilityOfHeads(vector<double>& prob, int target) { const int n = prob.size(); vector<double> dp(target + 1); dp[0] = 1.0; for (int i = 0; i < n; ++i) for (int j = min(i + 1, target); j >= 0; --j) dp[j] = dp[j] * (1 - prob[i]) + (j > 0 ? dp[j - 1] : 0) * prob[i]; return dp[target]; } }; |
Solution 2: Recursion + Memorization
Time complexity: O(n^2)
Space complexity: O(n^2)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// Author: Huahua class Solution { public: double probabilityOfHeads(vector<double>& prob, int target) { vector<vector<double>> mem(prob.size() + 1, vector<double>(target + 1, -1)); function<double(int, int)> dp = [&](int n, int k) { if (k > n || k < 0) return 0.0; if (n == 0) return 1.0; if (mem[n][k] >= 0) return mem[n][k]; const double p = prob[n - 1]; return mem[n][k] = p * dp(n - 1, k - 1) + (1 - p) * dp(n - 1, k); }; return dp(prob.size(), target); } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment