Toss Strange Coins - Implementation

Full table: $O(nk)$ space. But each row only depends on the previous row. Use two arrays: $prev$ and $curr$. Swap after each coin. Space: $O(k)$. Or use single array with reverse iteration: $dp[j] = dp[j-1] \cdot p_i + dp[j] \cdot (1-p_i)$, iterating $j$ from $k$ down to $1$. Time: $O(nk)$, Space: $O(k)$. The pattern is identical to 0/1 Knapsack space reduction. Space reduction works because each row only depends on the previous row. You can use two arrays or reverse iteration.