Educational DP Contest：B - Frog 2

問題

atcoder.jp

解法

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

と定義する．このとき，

dp(i) = min( dp(i - j) + | h_i - h_(i - j) | ) (1 <= j <= K)

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

解答

atcoder.jp