DP全然わからんなのでEDPCをはじめからていねいにやっていく。

A - Frog 1

問題文

$$N$$個の足場があります。 足場には$$1,2,…,N$$と番号が振られています。
各$$i(1≤i≤N)$$について、足場$$i$$の高さは$$h_i$$です。

最初、足場$$1$$にカエルがいます。カエルは次の行動を何回か繰り返し、足場$$N$$まで辿り着こうとしています。

足場$$i$$にいるとき、足場$$i+1$$または$$i+2$$へジャンプする。このとき、ジャンプ先の足場をjとすると、コスト$$|hi − hj|$$を支払う。

カエルが足場$$N$$に辿り着くまでに支払うコストの総和の最小値を求めてください。

制約

• 入力はすべて整数である。
• $$2≤N≤10^5$$
• $$1≤h_i≤10^4$$

どういうこと？

足場$$i$$に辿り着くまでのコストの総和の最小値が知りたいのでDPテーブルはこうなる。

dp[i]は、足場$$i+1$$に辿り着くまでに支払うコストの総和の最小値

今回は最小値が知りたいので、DPテーブルはINF(大きい値)で初期化する。

dp[0](足場1)に辿り着くためのコストは、移動がないので明らかに0。
dp[1](足場2)に辿り着くためのコストは、足場1から移動するしか方法がないため$$|h1 − h2|$$になる。

次に足場3以降の遷移を考える。
カエルは、2つの行動ができる

• 足場$$i - 1$$ → 足場$$i$$ への移動
• 足場$$i - 2$$ → 足場$$i$$ への移動

重要なのは、足場$$i - 1$$に辿り着くまでのコストがいくらであろうと、そこから足場$$i$$までの移動にかかるコストにはなんの関係ないということ。
足場$$i - 2$$から足場$$i$$への移動についても同じ。

ということは、

• 足場$$i - 1$$ → 足場$$i$$ へ移動する時のコスト = $$|h{i-1} − hi|$$
• 足場$$i - 2$$ → 足場$$i$$ へ移動する時のコスト = $$|h{i-2} − hi|$$

このふたつを比べて、小さい方をdp[i]の値とすればいい。

n = gets.to_i
hs = gets.strip.split.map(&:to_i)

# 大きいコスト
inf = 10 << 60

# dp[i]は、足場i+1に辿り着くまでに支払うコストの総和の最小値
dp = Array.new(n, inf)

# 足場1に辿り着くまでに支払うコストの総和の最小値は明らかに0
dp[0] = 0

# 足場2に辿り着くまでに支払うコストの総和の最小値は明らかに(hs[1] - hs[0]).abs
dp[1] = (hs[1] - hs[0]).abs

# 足場3〜足場n-1についてDPテーブルを埋める
(2...n).each do |i|
    dp[i] = [dp[i], dp[i - 1] + (hs[i] - hs[i - 1]).abs].min
    dp[i] = [dp[i], dp[i - 2] + (hs[i] - hs[i - 2]).abs].min
end

puts dp[n - 1]

感想

足場が足湯に見えてきた。

本当は初期化するのはdp[0]だけで十分で、(2...n).eachとしているところをn.timesにしてもいい。

その場合は配列の範囲外のインデックスを参照してしまわないように、ループの中でif i > 0とif i > 1の条件が必要になる。

添え字が何を意味してるのかがあやふやになると「DP全然わからん」状態になってしまうんだろうなと思う。