DPについての講義を受けた記録（前編）

恥ずかしながら未だにDP（動的計画法）に慣れてないのでどうしたものかなと思っていたら「DPなら俺に任せろ。俺はDPの気持ちが分かる」という方が居られたのでそれならと知人と共に簡単な講義をお願いした。「ちょっと張り切って作ってみた」と聞いていたので少しビビりながらも当日に臨んだのでその記録。この内容は入門レベルなので読む必要ない人の方が多いはず。

導入

DPとはなんぞや

Wikipediaには以下の2つの条件を満たすものと書いてある。

• 分割統治法
• メモ化

しかし、講義内ではもう少し厳密さを入れたかったのか、ボトムアップに解いていく点も説明に含められていた。まとめると講義では、「部分問題をボトムアップに解いていく」、「同じ計算を二度実行しない」の二点が何度も繰り返された。

その後、フィボナッチ数列を例に説明が為された。

フィボナッチをDPで解く例

演習1（ロッド切り出し問題）

ロッド切り出し問題を使った演習。漸化式を見つけると言う分かりきった分かりにくいものだけではなく、部分最適構造性を見つけるということで含まれていたSchemeの例がわかりやすかった。

長さが5の時は、5, (4, 1), (3, 2)の3パターンだが、1から順に入力値までの最適解を求めながらループさせることになる。

コード例

演習2（LCS）

定番のLCSを使った演習。この漸化式見つけられるならそもそも困らないだろと皆がツッコみたいところである。仮定が大事という言葉にうまく丸め込まれた感は否めない。

仮定→漸化式→プログラム、という風に落としこんでいく感じは掴めた（気がする）。

コード例

所感

こういう機会を設けることに意味はあるが、仕事ではあまり使わない現実が悲しい。

久しぶりに書いたけど、Blogger使いづらい。

→DP講義（後編）は11/30開催予定