Educational DP Contest A - Frog 1【Pythonの解答例】 - ebisukeプログラミング初心者脱出黙示録

f:id:ebisuke33:20210322210400p:plain
ABC184のD問題を解くためにDPの学習方法を探していたところ、Educational DP Contest（EDPC）の存在を知りました。
ちょうどよい機会でしたのでEDPCを進めていきたいと思います。

DPについてはこちらの記事で勉強しました。大変助かりました。
動的計画法超入門！ Educational DP Contest の A ～ E 問題の解説と類題集 - Qiita

EDPC A - Frog 1

A - Frog 1

問題文

N個の足場があります。足場には1,2,…,Nと番号が振られています。各i(1≤i≤N) について、足場iの高さはhiです。
最初、足場1にカエルがいます。カエルは次の行動を何回か繰り返し、足場Nまで辿り着こうとしています。
足場iにいるとき、足場i+1またはi+2へジャンプする。このとき、ジャンプ先の足場をjとすると、コスト|hi−hj|を支払う。
カエルが足場Nに辿り着くまでに支払うコストの総和の最小値を求めてください。

制約

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

解答例

n = int(input().strip())
h = list(map(int, input().strip().split()))

dp = [0] * 100010 # (※1)制約条件の足場数より多い要素数の配列を準備

dp[0] = 0 # (※2)初期条件
dp[1] = abs(h[1] - h[0])

if n > 2:
    for i in range(2,n):
        dp1 = dp[i-1] + abs(h[i] - h[i-1]) # (※3)足場i-1から足場iへ移動したときのコスト
        dp2 = dp[i-2] + abs(h[i] - h[i-2]) # (※4)足場i-2から足場iへ移動したときのコスト
        if dp1 > dp2:
            dp[i] = dp2
        else:
            dp[i] = dp1

print(dp[n-1])

解説

次の足場へジャンプ(移動)するごとに高さにおうじたコストがかかるカエルが、目標の足場まで最も少ないコストで移動する方法を求める問題です。
下の絵のように足場iから足場i+1(青線)か足場i+2(赤線)のどちらかに移動できます。
f:id:ebisuke33:20201126220245p:plain
iからi+2へ移動したほうが、移動回数が減るのでコストは減りそうですが、足場の高さによっては逆にコストがかかることも考えられます。
このような問題でDPという手法が使えます。
※1のように想定される足場の数より多い要素数の配列dpを準備します。dp[i]は足場i+1まで移動するときの最小コストを書き込んでいきます。
※2では初期条件としてdp[0]つまりスタート地点のコストを代入しました。スタート時点ではまだ動いていないのでコストは0です。
次の行ではスタート地点の次の足場に移動するコストをdp[1]に代入しています。その後のループの条件分けが面倒だったためです。
足場の数Nが2の場合はdp[1]が解答となり、Nが2より大きければfor文でdp[i]を求めていきます。
※3 dp1は隣の足場i-1から足場iに移動するとき必要なコストを求めています。スタート地点から足場i-1までの移動コストdp[i-1]に、足場i-1からiに移動するときのコストを足すことで求められます。
※4 dp2は足場i-2から1つ飛ばしで足場iに移動するときのコストを求めています。
このdp1とdp2を比較して小さいほうをdp[i]に代入することで足場iまでの最小コストがわかります。
この作業を繰り返すことで目的の足場Nまで移動するときの最小コストdp[i-1]が求まります。
最後にdp[i-1]を出力してACとなりました。