動的計画法 その１

イントロダクション 動的計画法（Dynamic Programing：以下「DP」と記述）は，ある種の最適化問題を効率的に（少ない計算時間で）解くための方法である。 アルゴリズム関連の参考書籍では，次のように説明される。 k 個の要素だけをとったときの最適解が表の形で与えられているとする。これに要素を1個付け加えたときに，最適解がどのように変わるかをこの表をもとに計算し，表を書き換える。 この操作を続けて，n 個の要素すべてを使った最適解が求まればよい。表の添え字としては，問題の性格を規定するパラメータのうち要素の個数以外のものを選ぶ。