dynamic programming

dynamic programmingは、大きな問題を小さな部分問題に分割し、一度計算した結果を再利用することで効率的に答えを導き出す手法です。単なる再帰的な処理とは異なり、計算済みの値を保存しておくメモ化や、ボトムアップ形式で解を積み上げる手法を用いるため、計算時間を大幅に削減できるのが特徴です。

再帰的アプローチとの違い

単純な再帰処理では、同じ部分問題を何度も繰り返し計算するため、問題の規模が大きくなると計算量が爆発的に増加します。一方でdynamic programmingは、一度得られた解を記憶して再利用するため、重複した計算を排除できます。例えば、フィボナッチ数列の計算において、単純な再帰ではなくdynamic programmingを用いることで、計算量を指数関数的なレベルから線形的なレベルまで抑えることが可能です。

適用条件と活用例

この手法を適用するには、問題が最適部分構造（大きな問題の最適解が、小さな部分問題の最適解から構成されていること）と重複する部分問題（同じ計算が何度も現れること）という二つの特性を持っている必要があります。実務的な活用例としては、以下のようなケースが挙げられます。

最短経路問題（ダイクストラ法など）
文字列の編集距離の計算
ナップサック問題などの最適化問題