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

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.

Knapsack Variant via Top Down Dynamic Programming – Multiple Coin Probability Toss

This Knapsack variant is quite similar to: Teaching Kids Programming – Find Partition Equal Subset Sum (Top Down Dynamic Programming Algorithm).

For each coin – we have p[i] probability to let it face up then we have k-1 coins left to be facing up. Or we have (1-p[i]) to let it face down and then we still have k coins left to be facing up.

Let f(i, h) represents that we are tossing i-th coin and have h heads as our target. And we have two choices:

When we have tossed/flipped all coins the probability should be one if the balance is zero otherwise should be zero.

We can implement this using Recursion with Memoziation aka Top Down Dynamic Programming Algorithm.

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def knapsackVariantMultipleCoinsToss(self, prob, target):
        n = len(prob)
        if target > n:
            return 0
        @cache                                         
        def f(i, h):
            if i == len(prob):
                return 1 if h == 0 else 0
            choose = prob[i] * f(i + 1, h - 1)
            skip = (1 - prob[i]) * f(i + 1, h)
            return choose + skip
        return f(0, target)

class Solution:
    def knapsackVariantMultipleCoinsToss(self, prob, target):
        n = len(prob)
        if target > n:
            return 0
        @cache                                         
        def f(i, h):
            if i == len(prob):
                return 1 if h == 0 else 0
            choose = prob[i] * f(i + 1, h - 1)
            skip = (1 - prob[i]) * f(i + 1, h)
            return choose + skip
        return f(0, target)

The time and space complexity is both as for each state (i, h) we calculate once and store it. We can start backwards from the end – which should give us:

And we start from the end aka f(n-1, k).

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def knapsackVariantMultipleCoinsToss(self, prob, target):
        n = len(prob)
        if target > n:
            return 0
        @cache
        def f(i, h):
            if i < 0:
                return 1 if h == 0 else 0
            choose = prob[i] * f(i - 1, h - 1)
            skip = (1 - prob[i]) * f(i - 1, h)
            return choose + skip
        return f(len(prob) - 1, target)       

class Solution:
    def knapsackVariantMultipleCoinsToss(self, prob, target):
        n = len(prob)
        if target > n:
            return 0
        @cache
        def f(i, h):
            if i < 0:
                return 1 if h == 0 else 0
            choose = prob[i] * f(i - 1, h - 1)
            skip = (1 - prob[i]) * f(i - 1, h)
            return choose + skip
        return f(len(prob) - 1, target)       

We can proactively store/remember the values in array: Teaching Kids Programming – Multiple Strange Coin Flips/Toss Bottom Up Dynamic Programming Algorithm (Knapsack Variant)

Knapsack Problems

• Teaching Kids Programming - 0/1 Knapsack: Length of the Longest Subsequence That Sums to Target (Recursion+Memoization=Top Down Dynamic Programming)
• Teaching Kids Programming - 0/1 Knapsack Space Optimised Dynamic Programming Algorithm
• Teaching Kids Programming - Using Bottom Up Dynamic Programming Algorithm to Solve 0/1 Knapsack Problem
• Teaching Kids Programming - 0/1 Knapsack Problem via Top Down Dynamic Programming Algorithm
• Teaching Kids Programming - Multiple Strange Coin Flips/Toss Bottom Up Dynamic Programming Algorithm (Knapsack Variant)
• Teaching Kids Programming - Multiple Strange Coin Flips/Toss Top Down Dynamic Programming Algorithm (Knapsack Variant)
• Teaching Kids Programming - Max Profit of Rod Cutting (Unbounded Knapsack) via Bottom Up Dynamic Programming Algorithm
• Teaching Kids Programming - Max Profit of Rod Cutting (Unbounded Knapsack) via Top Down Dynamic Programming Algorithm
• Teaching Kids Programming - Brick Layout (Unlimited Knapsack) via Bottom Up Dynamic Programming Algorithm
• Teaching Kids Programming - Brick Layout (Unlimited Knapsack) via Top Down Dynamic Programming Algorithm
• Count Multiset Sum (Knapsacks) by Dynamic Programming Algorithm
• Count Multiset Sum (Knapsacks) by Recursive BackTracking Algorithm
• Dynamic Programming Algorithm to Solve the Poly Knapsack (Ubounded) Problem
• Dynamic Programming Algorithm to Solve 0-1 Knapsack Problem
• Classic Unlimited Knapsack Problem Variant: Coin Change via Dynamic Programming and Depth First Search Algorithm
• Classic Knapsack Problem Variant: Coin Change via Dynamic Programming and Breadth First Search Algorithm
• Complete Knapsack Problem
• 0/1 Knapsack Problem
• Teaching Kids Programming - Combination Sum Up to Target (Unique Numbers) by Dynamic Programming Algorithms
• Algorithms Series: 0/1 BackPack - Dynamic Programming and BackTracking
• Using BackTracking Algorithm to Find the Combination Integer Sum
• Facing Heads Probabilties of Tossing Strange Coins using Dynamic Programming Algorithm
• Partition Equal Subset Sum Algorithms using DFS, Top-Down and Bottom-up DP

–EOF (The Ultimate Computing & Technology Blog) —