人権なし

青コーダーの競プロで解いた問題や開発の進捗などの記録です

Educational DP Contest:H - Grid 1

問題

atcoder.jp

解法

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).

解答

atcoder.jp

コンテストの中盤にきていきなり基本的な問題だと感じた.

f:id:babcs2035:20190107170326p:plain