Teaching Kids Programming – Multiple Strange Coin Flips/Toss Bottom Up Dynamic Programming Algorithm (Knapsack Variant)

ACMer

3 years ago

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a list of floats chances and an integer target. Each element chances[i] represents the probability that the ith coin lands heads on a flip. Given that we throw each coin once, return the probability that exactly target number of them land heads.

Constraints
n ≤ 1,000 where n is the length of chances
0 ≤ chances[i] ≤ 1
0 ≤ target ≤ 1,000
Example 1
Input
chances = [0.5, 0.4]
target = 2
Output
0.2
Explanation
First coin has 50% chance of heads while the second has 40% chance. So the chance they both land heads is 0.5 * 0.4 = 0.2

Example 2
Input
chances = [1, 0]
target = 1
Output
1
Explanation
The first coin will always land heads while the second will always land tails.

Hints:
in each step, you have 2 options: heads and tails (1-P(H)), recurse on all possible cases + memorize

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

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.

Multi Coin Flip/Toss by Bottom Up Dynamic Programming Algorithm (Knapsack Variant)

In Top Down, we use the magic keyword @cache to ask the computer remember the values that it has known/computed. In Bottom Up – we proactively remember the values in array.

Each dfs(i, k) corresponds to f[i][k] which is 2-D array. When k is larger than i, the probability is zero. We are filling a table where horizontal values are K, and vertical values (rows) are coins. To compute the f[i][k] value we need f[i-1][j-1] and f[i-1][j] values – which can be stored in array. In Top Down DP, these two values are stored by @cache.

class Solution:
    def knapsack(self, prob, target):
        if not prob:
            return 0 if target == 1 else 1
        n = len(prob)
        if target > n:
            return 0            
        f = [[0 for _ in range(len(prob) + 1)] for _ in range(n)]
        f[0][1] = prob[0]
        f[0][0] = 1 - prob[0]
        for i in range(1, n):
            f[i][0] = f[i - 1][0] * (1 - prob[i])
            for j in range(1, i + 2):   # j-1<=i-1 and j<=i-1
                f[i][j] = f[i - 1][j] * (1 - prob[i]) + f[i - 1][j - 1] * prob[i]
        return f[n - 1][target]

class Solution:
    def knapsack(self, prob, target):
        if not prob:
            return 0 if target == 1 else 1
        n = len(prob)
        if target > n:
            return 0            
        f = [[0 for _ in range(len(prob) + 1)] for _ in range(n)]
        f[0][1] = prob[0]
        f[0][0] = 1 - prob[0]
        for i in range(1, n):
            f[i][0] = f[i - 1][0] * (1 - prob[i])
            for j in range(1, i + 2):   # j-1<=i-1 and j<=i-1
                f[i][j] = f[i - 1][j] * (1 - prob[i]) + f[i - 1][j - 1] * prob[i]
        return f[n - 1][target]

The time complexity is or where K is no more than N. And the space complexity is or .