Dynamic Programming を一文で説明してみる。2017年03月24日 19時17分33秒

Dynamic Programming は「大きな問題をいくつもの細かい問題に分けて解いていく方法」。

小さい子供達にも、教えられるようにと思って、簡潔な言葉でまとめてみることにした。少々語弊が入るかも知れないが、そこはある程度目をつぶって。

以前からこの名前の付け方は、芳しくないと思っていた。日本語では「動的計画法」などと言われる。時折、あれ、どんな技法だったけと、忘れてしまう。

簡単に要約すると、「分割統治法」。Divide and Conquer と言われる、大きな問題を小さな問題郡に分けて、単純化して再帰的に解くと言うこと。また、この再帰時に、前回求めた結果を再利用する「メモ化」も技法の一部に入る。