水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

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

f:id:babcs2035:20190107163406p:plain