Pocalaメモ

アウトプット用のなにか

トップ > 単語・概念 > DP（動的計画法）が何か分からない

DP（動的計画法）が何か分からない

単語・概念

そもそもDPとは？

Dynamic Programmingの略。日本語では動的計画法という。
DPは「回転技」のような分類の一つ。一つの具体的な技の名称ではなさそう。

DPを満たす条件

  1. 分割統治法を使っている
  2. メモ化を使っている

の2つ。これを満たしていたらDPだったりする。DPは幅が広いっぽい。

分割統治法って？

分割統治法は、divide and conquer です。問題を細かく分割して、それぞれを計算した後にすべてを合体したら答えになるってやつです。
イメージとしては、マージソートをイメージすると早いかもです。動画を見るのがオススメです。

メモ化って？

メモ化は、名前の通りメモします。つまり、「一度計算したことを二度と計算したくないので結果を紙に書いて再利用します」ていうやつ。
イメージとしては、「『7! + 8! + 9!』 を計算するときに、7!だけ計算(5040)しておいたら、8!はそれに8を掛けて40320になるし、同様に9!は40320に9を掛ければあとはそれぞれを足せば楽だよね」みたいな考え方が近いです。（全て1から計算しなおす人はいないと思ってるけど…）

DPは結局どんな考え方？

つまりDP（動的計画法）のベースとなる考え方は、「再帰っぽい考え方で解いていくけど、同じ計算を二度としたくないので値を記録しながらがんばります」です（多分）。

DPは基本的には２種類の方法がある

トップダウンの方は再帰的というだけあって再帰の知識が必要。それにメモ化を加える感じ。
ボトムアップの方は漸化式を使うらしい。漸化式って何だ。

よくDPの入門系のサイトの例題で挙がるのがフィボナッチ数列。「８番目のフィボナッチ数を求めよ」みたいなときに、

  • トップダウン→fib(n) = fib(n-1) + fib(n-2) のnの所に8を入れて再帰を使って上から下に求めていく。
  • ボトムアップ→1+1+2+3…のように下から順に計算していって8番目を求める。

みたいな感じで解法が変わってくる（多分）。

DPの基本的なパターンは3つ

DPを使うパターンとしては、

  • ナップサック DP
  • 区間 DP
  • bit DP

の3つがあるそうです（基本）。ちなみに自分は全く解けたことがない（2018年12月現在）ので、詳しいことはまだ言えませんが、た…ぶん、けんちょんさんの
qiita.com
などが役に立つと思います、はい。

感想

 再帰も漸化式も操れない自分にとってはDPを扱うにはハードルが高く見えますが、頑張ります。