DPができるようになりたい Part1

こんばんは、ぱんと申します。

昨日のABC参戦記のD問題をまだ書ききっていないんですが、解けなかったE問題について気になっちゃったのでそっちを先にやります。
昨日の記事↓

聞くところによると、このABC153のE問題がDPらしいんですよ。言葉は聞いたことあるしコードもなんとなく見たことあるけど、解けないし「これDPで解ける！」とも言えないので、解けるようになるぞー！って記事です。いつ終わるんかな。

てかまずDPってなんですか

優秀なWikipedia先生のお言葉を借りると

動的計画法（どうてきけいかくほう、英: Dynamic Programming, DP）は、計算機科学の分野において、アルゴリズムの分類の1つである。対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法を総称してこう呼ぶ。

…ほーん、分からん。Wiki先生によると、

トップダウン方式…計算結果を記録(メモ化)して再利用する方法
ボトムアップ方式…先に部分問題を解いていく方法

の2つに分かれるらしいけど……

とりあえずやってみよう

「DPの練習問題とかまあ探せば転がってるでしょ」と思って探したらドンピシャのものがありました。インターネット、すごい(語彙力)。

動的計画法超入門！ Educational DP Contest の A ～ E 問題の解説と類題集 - Qiita

DPの典型問題を集めたコンテストであるEducational DP Contestというのが開かれたらしく、上のサイトはその問題解説をしてくれているんですね。このコンテストでは、A～Zの26個の問題があるみたいです。早速A問題から解いてみます。

A問題を解く

A - Frog 1

カエルが足場1からNに行きたい。移動方法は

N-1番→N番(隣の足場へ)
N-2番→N番(1個飛ばし)

のどちらか。
足場にはそれぞれ高さh_iがあり、足場iから足場jへの移動にはコスト|h_i - h_j|がかかる。このとき足場Nまで行くのに必要な最小コストを求めよ、という問題。

上の記事を参考にしながら、Pythonで書いてみました。→実際の提出

コメントなし

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

dp = [float('inf') for i in range(n)]
dp[0] = 0

dp[1] = min(dp[1], dp[0] + abs(h[1] - h[0]))

for i in range(2, n):
 dp[i] = min(dp[i], dp[i - 1] + abs(h[i] - h[i - 1]))
 dp[i] = min(dp[i], dp[i - 2] + abs(h[i] - h[i - 2]))
 
print(dp[n-1])

コメントあり

# 入力を拾う
n = int(input())
h = list(map(int, input().split()))

# dpテーブルの初期値設定
dp = [float('inf') for i in range(n)]
dp[0] = 0

# n=1の場合だけ別枠で計算
dp[1] = min(dp[1], dp[0] + abs(h[1] - h[0]))

# for文ぐるぐる
for i in range(2, n):
 dp[i] = min(dp[i], dp[i - 1] + abs(h[i] - h[i - 1]))
 dp[i] = min(dp[i], dp[i - 2] + abs(h[i] - h[i - 2]))
 
# 欲しい答えを出力
print(dp[n-1])

考察

まあ上の記事を見てもらえばほぼそのままなんですけど、記事にあったchmin()という関数を単純にminで代用しました。今後難しい問題にあたったとき、必要になってくるのかな…？

〇初期値設定について
初期位置である足場1にいるときのコスト(dp[0])は0。
今回は「最小コスト」を求める問題なので、それ以外のdp[i]の初期値はinfにしておきます(あとで小さいコストを確実に代入するため)。

〇i=1の場合
2つ隣からくるのと1つ隣からくるのでどっちがコストが小さいか比較したいですが、i=1の場合、つまり足場2にいる場合は2つ隣からの移動は考えないので別枠で計算しています。

〇for文
あとは単純に2つ隣からくるのと1つ隣からくるのでどっちがコストが小さいか比較。わざわざinfであるdp[i]を持ってきて2回比較する必要あるのかなって感じですが、まあこの書き方がDPの型なのかな、と思ってそのまま受け入れました。

〇出力
で、最後は欲しいものをprint。今dp[n-1]が足場Nでの最小コストになっていることに注意。

感想

・意外となんとかなる気がしてきた
・DPたのしい
・難しい問題になると重いPythonでは解けなくなって詰みそう。Java先生のおべんきょうをしなくちゃ。

というわけで次回はB問題に挑戦します。

最後まで読んでいただきありがとうございます。またどうぞ。