読み方：どうてきけいかくほう

動的計画法【Dynamic Programming】DP

動的計画法とは？

複雑な問題を小さな部分問題に分割し、それぞれの解を記録・再利用しながら全体の最適解を求めるアルゴリズム設計の手法である。1950年代にリチャード・ベルマン（Richard E. Bellman）が考案した。

動的計画法の基本的な方針は「同じ計算を繰り返さない」ことである。例えば、フィボナッチ数列の第50項を求める場合、単純な再帰処理では同じ項を何度も計算し直すため、計算量が爆発的に増大する。動的計画法では、一度求めた部分問題の答えをテーブルに記録しておき、同じ計算が必要になったときはそのテーブルを参照するだけで済ませる。この記録・再利用の仕組みを「メモ化」と呼ぶ。

動的計画法が適用できる問題には、二つの条件がある。一つ目は「最適部分構造」と呼ばれる性質を備えていることで、全体の最適解が部分問題の最適解の組み合わせで構成されることを意味する。二つ目は「重複する部分問題」で、解を求める過程で同じ部分問題が繰り返し登場することを指す。この二条件を満たす問題であれば、動的計画法によって処理時間を大幅に短縮できる。

様々な問題に適用することができ、最短経路問題、文字列の類似度を測る編集距離の計算、ナップサック問題（限られた容量に価値を最大化するよう荷物を詰める組み合わせ最適化）、DNAの塩基配列解析などで応用されている。競技プログラミングでも頻出の手法であり、コンピュータ科学を学ぶ上で避けて通れない考え方である。