Facing Heads Probabilties of Tossing Strange Coins using Dynamic Programming Algorithm

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.

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.

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:

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.

Knapsack Problems

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...

766 words
Last Post: How to Find the Missing Number In Arithmetic Progression?
Next Post: How to Find the Length of the Longest Increasing Subsequence using Dynamic Programming Algorithm?

The Permanent URL is: Facing Heads Probabilties of Tossing Strange Coins using Dynamic Programming Algorithm

Algorithms, Blockchain and Cloud

Facing Heads Probabilties of Tossing Strange Coins using Dynamic Programming Algorithm

Depth First Search Algorithm to Calculate the Toss Probabilities

Using Dynamic Programming Algorithm to Compute the Probabilties of Tossing a Coin

Knapsack Problems

Leave a Reply

Depth First Search Algorithm to Calculate the Toss Probabilities

Using Dynamic Programming Algorithm to Compute the Probabilties of Tossing a Coin

Knapsack Problems

Related posts:

Leave a Reply