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)．
解答
コンテストの中盤にきていきなり基本的な問題だと感じた．
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)．
コンテストの中盤にきていきなり基本的な問題だと感じた．