source: https://leetcode.com/problems/toss-strange-coins/description/
Toss Strange Coins
Table of Contents
Description
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
|
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(double[] prob, int target) { Double[][] memo = new Double[prob.length+1][prob.length+1]; return dfs(prob, target, 0, 1.0, memo); } public double dfs(double[] prob, int target, int index, double p, Double[][] memo){ if (target < 0) return 0; if(index>=prob.length){ if(target==0){ return 1; } return 0; } if(memo[target][index]!=null) return memo[target][index]; double sum = 0; //either heads sum = prob[index]*dfs(prob, target-1, index+1, p*prob[index], memo); sum += (1-prob[index])*dfs(prob, target, index+1, p*(1-prob[index]), memo); memo[target][index]=sum; return sum; } } |