Pythonで動的計画法(Dynamic Programming)を実装してみる
この記事ではPythonを使って動的計画法(DP)の問題を解いていきます。
本記事ではこれから動的計画法の勉強を始める入門者向けに解説していきます。
動的計画法のイメージをつかむために簡単な問題を解いていきますので、がっつりDPを勉強をしたい人にとっては物足りないかもしれないのでご注意ください。
また、動的計画法は難易度が高めのアルゴリズムなので「AtCoderで茶色になりたい！」という人は動的計画法よりも累積和やDFSなどの勉強を先にすることをおすすめします。
動的計画法とは
動的計画法は問題を複数の部分問題に分割し、計算結果を記録しながら解いていく手法のことを言います。
似たような手法として貪欲法というアルゴリズムがあります。貪欲法も問題を部分問題に分割して考えるアルゴリズムです。
では、貪欲法と動的計画法は何が違うのかというと、保持する状態の数が違います。
貪欲法は保持する状態は一つだけですが、動的計画法は2つ以上保持することができます。
このため貪欲法の方が実装においては簡単ですが、最適解が得られない可能性があります。
とはいえ、問題を部分問題に分割して考えるという点では動的計画法と貪欲法は似ているので、もし貪欲法を知らないのであればまず貪欲法を勉強してから動的計画法を勉強した方がいいかもしれません。
nashidos.hatenablog.com
例題
今回は以下の問題を扱います。
atcoder.jp
問題文
N 個の足場があります。 足場には 1,2,…,N と番号が振られています。 各 i (1≤i≤N) について、足場 i の高さは hiです。
最初、足場 1にカエルがいます。 カエルは次の行動を何回か繰り返し、足場 Nまで辿り着こうとしています。
・足場 iにいるとき、足場 i+1 または i+2 へジャンプする。 このとき、ジャンプ先の足場を j とすると、コスト |hi−hj|を支払う。
カエルが足場 Nに辿り着くまでに支払うコストの総和の最小値を求めてください。
制約
入力はすべて整数
2≤N≤105
1≤hi≤104
実装
この問題に動的計画法を当てはめて言い換えると
「1回ずつの移動という部分問題に分割して２パターンの移動コストを記録していく」
という風に言うことができます。
1回ずつの移動でカエルは以下の2つの方法を選ぶことができます。
・足場i+1に移動する
・足場i+2に移動する
では実際に1回ずつの移動という部分問題に分割して考えてみましょう。
まずはスタート地点のコストを記録します。スタート地点なのでもちろんコストは0です。
そして次は足場2に移動する時を考えます。
足場2に移動する方法は足場1から移動するしかないのでコストはabs(足場1の高さ - 足場2の高さ)になります。
次に足場3に移動する方法としては
・足場1から移動する
・足場2から移動する
という2つの移動方法があります。
この問題は支払うコストを最小化したいので2つの移動方法のコストが小さい方を選びます。
選ぶ時は今まで移動してきた時にかかったコストと一緒に選びます。
この操作を繰り返すことによって解を求めることができます。
実装の肝としては移動にかかったコストを記録し、それを再利用するところです。
以下が実装したコード例です。
n = int(input()) h = list(map(int,input().split())) dp = [0, abs(h[1]-[0])] for i in range(2,n): dp.append(min(dp[i-1] + abs(h[i]-h[i+1]), dp[i] + abs(h[i]-h[i+2]))) print(dp[-1])
