Toss Strange Coins

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:

class Solution {
    Double[][] dp;
    
    public double probabilityOfHeads(double[] prob, int target) {
        dp = new Double[prob.length + 1][target + 1];
        return helper(prob, 0, 0, target);
    }
    
    private double helper(double[] prob, int start, int n, int target) {
        if (dp[start][n] != null) return dp[start][n];
        if (n == target) {
            double p = 1.0;
            for (int i = start; i < prob.length; i ++) {
                p = p * (1 - prob[i]);
            }
            return dp[start][n] = p;
        } else if (start == prob.length) {
            return dp[start][n] = 0.0;
        }
        double p = prob[start] * helper(prob, start + 1, n + 1, target) + (1 - prob[start]) * helper(prob, start + 1, n, target);
        return dp[start][n] = p;
    }
}