Leetcode 1230: Toss Strange Coins

https://leetcode.com/problems/toss-strange-coins/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.

Notes:

A very nice and potentially useful programming problem!

For programming, the key is to find the state transition.

let use f(id, target) represents the probability that we can achieve starting with index of id and ending with target heads.

Then we can write:

f(id, target) = prob[i] * f(id+1, target-1) + (1 - prob[i]) * f(id+1, target).

The physical meanings for the above two parts on the right side is very obvious:

1): if the id-th gives a head with a prob[i], then the rest needs to give (target - 1) heads;

2): if the id-th gives a tail with a prob (1 - prob[i]), then the rest needs to give target heads;

In the programming point of view, in both cases, id is becomes larger, or converging to a base case. So it is programmable. In addition, following this line, we can figure out the base case.

Another important issue is the time complexity. If we run the above formula directly, it will give factorial complexity, which is too much. Actually we have re-calculated many of the sub-state. So we can use memorization to avoid this.

The optimized time complexity can be O(Len*target).

See the code below:

class Solution {
public:
    double probabilityOfHeads(vector<double>& prob, int target) {
        int len = prob.size();
        vector<vector<double>> memo(len+1, vector<double>(target+1, -1));
        return dfs(prob, 0, target, memo);
    }

private:
    double dfs(vector<double>& ps, int id, int tar, vector<vector<double>>& memo) {
        if(id<0 || tar < 0 || tar > ps.size()) return 0;
        if(id == ps.size()) {
            if(tar == 0) return 1;
            return 0;
        }
        if(memo[id][tar] != -1) return memo[id][tar];
        return memo[id][tar] = ps[id]*dfs(ps, id+1, tar-1, memo) + (1-ps[id])*dfs(ps, id+1, tar, memo);
    }
};