readDP全然わからんなのでEDPCをはじめからていねいにやっていく。1問題文\(N\)個の足場があります。足場には\(1,2,...,N\)と番号が振られています。各\(i(1≤i≤N)\)について、足場\(i\)の高さは\(h_i\)です。最初、足場\(1\)にカエルがいます。カエルは次の行動を何回か繰り返し、足場\(N\)まで辿り着こうとしています。足場\(i\)にいるとき、足場\(i+1\)または\(i+2\)へジャンプする。h_j|\)を支払う。カエルが足場\(N\)に辿り着くまでに支払うコストの総和の最小値を求めてください。入力はすべて整数である。\(2≤N≤10^5\)\(1≤h_i≤10^4\)どういうこと?足場\(i\)に辿り着くまでのコストの総和の最小値が知りたいのでDPテーブルはこうなる。今回は最小値が知りたいので、DPテーブルはINF(大きい値)で初期化する。dp[0](足場1)に辿り着くためのコストは、移動がないので明らかに0。次に足場3以降の遷移を考える。1\)に辿り着くまでのコストがいくらであろうと、そこから足場\(i\)までの移動にかかるコストにはなんの関係ないということ。2\)から足場\(i\)への移動についても同じ。h_i|\)このふたつを比べて、小さい方をdp[i]の値とすればいい。足場が足湯に見えてきた。本当は初期化するのはdp[0]だけで十分で、(2...n).eachとしているところをn.timesにしてもいい。1の条件が必要になる。添え字が何を意味してるのかがあやふやになると「DP全然わからん」状態になってしまうんだろうなと思う。