動的計画法 - 大人になってからの再学習

アルゴリズムの学習をするなかで、「動的計画法」という用語が登場する。
よくある説明は、「ナップザック問題を解くのに使われる」とか、何か具体例を示して理解を促すものだけど、

そもそも動的計画法ってなに？

というところが、明確でなくて非常にわかりにくい。

わかりにくいのもそのはずで、そもそも動的計画法という名前のアルゴリズムや特定の手法があるわけではなくて、
動的計画法というのは、「考え方の名称」である。

「この問題は動的計画法で解きましょう」と言った時には、
「この問題は動的計画法的な考え方で解き方を別途考案しましょう」と読み替えるべき。

動的計画法は、あくまで「考え方」であるので、具体的な解き方（アルゴリズム）は、問題ごとにまったく異なるものになる。

繰り返しになるけど、動的計画法という名前のアルゴリズムがあるわけではない。

動的計画法の考え方とは
・大きな問題を小さな問題に分けて解く。
・一度、解いた問題の解は記憶しておいて、再利用する。
の2つだと思ってよい。

言われてみれば、何のことはない。特に難しい概念が登場するわけでもないので、なんでそんな名前を付けたんだろうかと疑問に思ってしまう。
英語で表現すると dynamic programming なので、もっとスゴイものを想像してしまいそうだ。

で、このような考え方をすると、簡単に問題が解けるよ、という例としてナップザック問題やらフィボナッチ数列の計算やらが挙げられることが多い、ということ。
もちろん、動的計画法に適さない問題も多いので、実際には「動的計画法の考え方で問題を効率的に解けるだろうか」ということを検討しつつ、じゃあ、どういうアルゴリズムにしますか、というのは別途、考え出す必要がある。