Toss Strange Coins - Problem Statement

$n$ coins with probabilities $p_i$ of heads. Find probability of exactly $k$ heads. $dp[i][j]$ = probability of $j$ heads in first $i$ coins. Transition: $dp[i][j] = dp[i-1][j-1] \cdot p_i + dp[i-1][j] \cdot (1 - p_i)$. Base: $dp[0][0] = 1$ (no coins, 0 heads).

Answer: $dp[n][k]$. This is the classic probability DP pattern. Each coin contributes independently, and we track the cumulative count. Each coin contributes independently. The product of individual probabilities gives the combined probability.