はじめに
動的計画法について学んだことを初心者視点でなるべく簡潔にまとめる
”Educational DP contest/DPまとめコンテスト（EDPC）”の問題を解くことを目標に進めていく
前回は簡単な問題で動的計画法を学んだ（動的計画法 (Dynamic Programming：DP) 学習メモ ～by Python～ Part 1）
今回はEDPCのA問題を解いていく
※※※ 参考にさせていただいた記事
動的計画法超入門！ Educational DP Contest の A ～ E 問題の解説と類題集
典型的な DP (動的計画法) のパターンを整理 Part 1 ～ ナップサック DP 編 ～
EDPC_A問題
①各足場に向かうために最適な行動をした場合に消費するコストを保存するリストを作成
dp = [0]*5
②1段目にいる場合は何も行動していないので当然コストは0
dp[0] = 0
③2段目 (高さ=h[1]) に移動する場合は1段目 (高さ=h[0]) からくるしかない。コストはh[1]-h[0]の絶対値
dp[1] = abs(h[1]-h[0])
④3段目 (高さ=h[2]) に移動する場合は
1⃣ 1段目(コスト=dp[0]) → 3段目
もしくは
2⃣ 2段目(コスト=dp[1]) → 3段目
の2通り。この二つの行動のコストを比較する。
1⃣の場合は1段目にいる場合の最小コスト dp[0] に h[2]-h[0] の絶対値を加えた数である
つまり、dp[0] + abs(h[2] - h[0])
2⃣の場合は2段目にいる場合の最小コスト dp[1]（②で計算した） に h[2]-h[1] の絶対値を加えた数である
つまり、dp[1] + abs(h[2] - h[1])
dp[2] = min(dp[0] + abs(h[2] - h[0]),dp[1] + abs(h[2] - h[1]))
⑤4段目 (高さ=h[3]) に移動する場合は
1⃣ 2段目(コスト=dp[1]) → 4段目
2⃣ 3段目(コスト=dp[2]) → 4段目
の2通り。
1⃣の場合は、dp[1] + abs(h[3] - h[1])
2⃣の場合は、dp[2] + abs(h[3] - h[2])
dp[3] = min(dp[1] + abs(h[3] - h[1]),dp[2] + abs(h[3] - h[2]))
⑥5段目 (高さ=h[4]) に移動する場合は
1⃣ 3段目(コスト=dp[2]) → 5段目
2⃣ 4段目(コスト=dp[3]) → 5段目
の2通り。
1⃣の場合は、dp[2] + abs(h[4] - h[2])
2⃣の場合は、dp[3] + abs(h[4] - h[3])
dp[4] = min(dp[2] + abs(h[4] - h[2]),dp[3] + abs(h[4] - h[3]))
以上を続けていく
列記してみる
dp = [0]*5
dp[0] = 0
dp[1] = abs(h[1]-h[0])
dp[2] = min(dp[0] + abs(h[2] - h[0]),dp[1] + abs(h[2] - h[1]))
dp[3] = min(dp[1] + abs(h[3] - h[1]),dp[2] + abs(h[3] - h[2]))
dp[4] = min(dp[2] + abs(h[4] - h[2]),dp[3] + abs(h[4] - h[3]))
for文に変えていく
dp = [0]*n
dp[0] = 0
dp[1] = abs(h[1]-h[0])
for i in range(1,n-1):
dp[i+1] = min(dp[i-1] + abs(h[i+1] - h[i-1]),dp[i] + abs(h[i+1] - h[i]))
for文のrangeは dp[n-1] まで求めたいため、range(1,n-1) → 例：n=5の場合は[1,2,3]
あとはリストの最後を出力すれば完成
EDPC_A解決
おわりに
B問題も同様の考え方で解けるが、解説能力の不足により簡単に以下にまとめる
移動元 i 範囲……(j-K)~(j-1)
移動先 j 範囲……1~n
移動先 j に対して、移動元は K 個分あるのだが、Kがjを超えてしまうと存在しない移動元 i が発生してしまう
そのため、存在しえない移動元 i を除く必要があるため、範囲の制限を加える必要がある
iの範囲は(max(0,j-K),j)
dp = [0] + [float('inf')]*(n-1)
for j in range(1,n):
for i in range(max(0,j-K),j):
dp[j] = min(dp[j],dp[i] + abs(h[j]-h[i]))