動的計画法

動的計画法とは、複雑な問題を、より小さな部分問題に分割し、それぞれの答えを記録しながら効率的に解くアルゴリズム手法です。再帰的に解を求める際に同じ計算を繰り返さないことで、計算量を劇的に減らせます。

部分問題の結果をテーブルなどに保存し、再利用することをメモ化と呼びます。全体の最適解を求める際に、段階的な最適解を積み上げていく考え方であり、最短経路問題やナップサック問題などで活用されます。

貪欲法との違いがポイントです。貪欲法は局所的な最適解を積み重ねますが、動的計画法は全体を考慮して最適解を導きます。試験では計算量の削減効果や、具体例としてどの問題に適しているかが問われます。