DP動的計画法とは、小さい部分問題を計算して記録しておき、より大きい問題を計算する際に利用する手法のことです。普通に計算すると同じ計算を何度も繰り返してしまい非効率であるようなアルゴリズムも、動的計画法を利用することで高速化することができます。いくつか具体例を見ながら、動的計画法の概念に慣れていきましょう。以下のような、前2つの数を足していくような並びの数列をフィボナッチ数列といいます。...漸化式で表すと以下の通りです。$$これの第n項を求める方法を考えてみましょう。動的計画法を使わないで計算する場合ナイーブに実装すると再帰関数を利用して以下のようになります。}}第n項を求めるために、第n-1項と第n-2項を再帰的に呼び出して計算する必要があるのですが、実は同じ計算を何度も行っているため非効率です。第5項を求める場合を例として考えてみましょう。上の図を見てもらうとわかりますが、fib(5)の計算をする際に、fib(3)の計算を2回行っています。今回はfib(5)の計算なのでこの程度で済んでいますが、求めたいフィボナッチ数が大きくなればなるほど、その無駄が無視できない大きさにまでなってしまいます。動的計画法を使う場合(メモ化再帰)一度計算したfib(n)の結果を配列などに保存しておき、既に計算したことのある値だったら再利用することにしましょう。これにより、無駄な計算が無くなって、かなりの高速化ができます。}}このような動的計画法の実装方法を、メモ化再帰などと言うことがあります。動的計画法を使う場合(漸化式)メモ化再帰は、再帰関数を使ってメモしていきましたが、直接配列の上で計算してしまっても構いません。0からn-2の時まで更新してやります。dp[i];}このような、漸化式を利用した動的計画法の実装方法もあります。動的計画法を使う有名な問題です。以下のような問に答えます。動的計画法を使わないナイーブな実装を考えてみましょう。荷物の入れ方を全探索し、重さBを超えないもので価値が最大となる時を出力すれば良いです。入れない」の2通りがあるので、全体で\(2^N\)通りあります。これは再帰関数を用いて計算することができます。番目の荷物を選択するかしないかで分岐させてください。i番目の荷物について考える。ret;}この場合、荷物の数Nが大きい場合、計算にかなりの時間がかかってしまいます。動的計画法を使う場合(メモ化再帰)先程のフィボナッチの例と同様に、動的計画法によって高速化させることができます。ナップサックのナイーブな再帰関数も、余計な計算があるので、メモ化再帰によって高速化ができます。結果を配列に保存しておき、2回目以降は再利用をしましょう。ret;}動的計画法を使う場合(漸化式)漸化式を使って同じ問題をどのように表現すれば良いか考えてみましょう。番目までの荷物の選び方で、最大となる価値の総和というのを漸化式を用いて表現してみましょう。値を考えてみましょう。よって漸化式は以下のようになります。番目までの荷物について、重さの総和がbまでとなるもので、価値の総和の最大値などとしても解くことができます。考え方から問題例まで徹底解説!競技プログラミングで良く用いられる動的計画法の1つ「桁DP」について解説します。コメントをキャンセルメールアドレスが公開されることはありません。*次回のコメントで使用するためブラウザーに自分の名前、メールアドレス、サイトを保存する。上に表示された文字を入力してください。