Educational DP Contest：I - Coins
問題
解法
dp(i, j) := i 枚目まで操作し j 枚表のときの，表が裏より多くなる確率
と定義する．このとき，
dp(i, j) = dp(i - 1, j + 1) * p_(i - 1) + dp(i - 1, j) * (1 - p_(i - 1))
と漸化式が立つ．状態数 O(N^2)，遷移 O(1) となり O(N^2)．
解答
確率漸化式を解かせるだけ．
dp(i, j) := i 枚目まで操作し j 枚表のときの，表が裏より多くなる確率
と定義する．このとき，
dp(i, j) = dp(i - 1, j + 1) * p_(i - 1) + dp(i - 1, j) * (1 - p_(i - 1))
と漸化式が立つ．状態数 O(N^2)，遷移 O(1) となり O(N^2)．
確率漸化式を解かせるだけ．