Coins (AtCoder DP I) | Probability DP Explained | 2D to 1D Space Optimization

In this video, we solve the 𝐂𝐨𝐢𝐧𝐬 problem from the 𝐀𝐭𝐂𝐨𝐝𝐞𝐫 𝐄𝐝𝐮𝐜𝐚𝐭𝐢𝐨𝐧𝐚𝐥 𝐃𝐏 𝐂𝐨𝐧𝐭𝐞𝐬𝐭 (𝐏𝐫𝐨𝐛𝐥𝐞𝐦 𝐈).⁣ ⁣ This problem explores a unique use-case of 𝐩𝐫𝐨𝐛𝐚𝐛𝐢𝐥𝐢𝐭𝐲-𝐛𝐚𝐬𝐞𝐝 𝐝𝐲𝐧𝐚𝐦𝐢𝐜 𝐩𝐫𝐨𝐠𝐫𝐚𝐦𝐦𝐢𝐧𝐠, where we are given the probabilities of getting heads for each coin, and we must calculate the probability of getting more heads than tails after flipping all coins.⁣ ⁣ We discuss:⁣ - Why a greedy or brute-force approach fails⁣ - How to build the recursive relation for probability DP⁣ - The bottom-up DP table construction⁣ - How we optimize space from 2D to 1D⁣ - And how to use fixed + setprecision(10) for precise answers⁣ ⁣ This problem is part of our dynamic programming series that goes from complete beginner to advanced level. Problems are taken from 𝐀𝐭𝐂𝐨𝐝𝐞𝐫, 𝐂𝐒𝐄𝐒, 𝐂𝐨𝐝𝐞𝐟𝐨𝐫𝐜𝐞𝐬, 𝐋𝐞𝐞𝐭𝐂𝐨𝐝𝐞, and more.⁣ ⁣ Problem link : https://atcoder.jp/contests/dp/tasks/dp_i⁣ ⁣ #AtCoderDP #ProbabilityDP #DynamicProgramming #CoinsDP #DPOptimization⁣