Educational DP Contest：A - Frog 1

問題

atcoder.jp

解法

 dp(i) := 足場 i に行くまでにかかるコストの最小値

と定義する．このとき，

dp(i) = min( dp(i - 1) + | h_i - h_(i - 1) |, dp(i - 2) + | h_i - h_(i - 2) | )

と漸化式が立つ．状態数 O(N)，遷移 O(1) となり O(N)．

解答

atcoder.jp