動的計画法とは
動的計画法（DP：Dynamic Programming）とは、大きな問題を解くために、それを小さな問題に分割して解き、その「途中の計算結果」をメモリなどに記録（メモ化）しておき、後で同じ計算が必要になったときに再利用するアルゴリズムの設計手法です。
同じ計算を何度も繰り返す無駄を省くことで、処理時間を劇的に短縮することができます。通常、再帰呼び出しと呼ばれる手法などでは、過去に解いたはずの同じ問題を何度もゼロから計算し直してしまいますが、動的計画法では一度計算した結果を「テーブル（表）」に保存しておき、二回目以降はそこから数値を呼び出すだけで済むようにします。
具体例
「フィボナッチ数列（前の2つの数字を足していく数列：1, 1, 2, 3, 5, 8, ...）」の10番目の数字を求めるプログラムを作る場合です。普通に計算すると「8番目を求めるために7番目と6番目を計算し、さらにその7番目のために6番目と5番目を計算し...」と同じ計算が何度も発生します。動的計画法では、1番目から順に計算結果を配列に保存していくため、同じ項の計算を一度も重複して行うことなく、最短で答えを求められます。
もう少し詳しく
動的計画法には、大きく分けて「トップダウン方式」と「ボトムアップ方式」の2つのアプローチがあります。「トップダウン方式」では、本来求めたい大きな問題からスタートし、再帰関数を用いて小さな問題へと分解していき、一度解いた小さな問題の答えを辞書や配列に記録（メモ化）して再利用します。一方、「ボトムアップ方式」では、最も単純な初期状態（基本ケース）から順番に計算を行い、結果をテーブルに埋めていきながら、最終的に求めたかった大きな問題の解へ到達します（一般的に狭義のDPテーブル構築はこちらを指します）。動的計画法を適用するための条件として、「部分構造最適性」（大きな問題の最適解が、分割された小さな問題の最適解を組み合わせて構成できること）と、「部分問題の重複」（小さな問題が何度も繰り返し現れること）の2点が必要とされます。
試験でのポイント
試験では、動的計画法の基本的な考え方を問う問題や、アルゴリズムの記述で穴埋めをさせる問題が出題されます。有名な適用例として、ナップサック問題（容量制限がある中で、価値の合計が最大になる荷物の組み合わせを求める問題）や、2つの文字列の類似度を測る「編集距離（レーベンシュタイン距離）」の計算、あるいは最短経路を求める「ワーシャル–フロイド法」などがあります。特にナップサック問題において、動的計画法を用いることで、全探索（O(2^N)）では到底解けない問題が、ナップサックの容量Wと荷物の個数Nの積である「O(NW)」の時間計算量で効率的に解けるようになるメリットを概念的に把握しておくことが重要です。
関連する用語
動的計画法に関連する用語としては、一度計算した結果を保存して再利用する「メモ化」や、大きな問題を再帰的に解くアプローチである「再帰呼び出し」があります。また、典型的な応用問題である「ナップサック問題」や、類似の最適化アルゴリズムである「貪欲法（グリーディアルゴリズム）」、さらに問題を分割して解く「分割統治法」との設計思想の違い（部分問題が重複するか否かなど）も深く関連しています。