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)．
解答
確率漸化式を解かせるだけ．
Educational DP Contest：H - Grid 1
問題
解法
dp(i, j) := マス (i, j) に到達するまでの経路数
と定義する．このとき，
dp(i, j) = 1 (i == 1 かつ j == 1 のとき)
dp(i, j) = dp(i - 1, j) + dp(i, j - 1) (それ以外のとき)
と漸化式が立つ．状態数 O(HW)，遷移 O(1) で O(HW)．
解答
コンテストの中盤にきていきなり基本的な問題だと感じた．
Educational DP Contest：G - Longest Path
問題
解法
dp(i) := 頂点 i から始まるパスで最長のものの長さ
と定義する．このとき，
dp(i) = max( dp(v) + 1 ) (v は頂点 i から到達できる任意の頂点)
と漸化式が立つ．答えは dp(i) (1 <= i <= N) の最大値．状態数 O(N)，遷移 O(N - 1) だけれども，各辺は高々 1 回しか見ないので O(N)．
解答
