動的計画法とは
動的計画法（どうてきけいかくほう）とは、複雑な問題を解くためのアルゴリズム設計手法の一つです。英語では「Dynamic Programming（DP）」と呼ばれます。この手法では、大きな問題をいくつかの小さな問題に分割し、それぞれの小さな問題の答えを一度だけ計算して、その結果をメモリなどに記録しておきます。そして、より大きな問題を解く際に、すでに記録してある計算結果を再利用することで、無駄な重複計算をなくし、処理効率を劇的に高めることができます。同じ計算を何度も繰り返してしまうような問題に対して、非常に強力な解決策となります。
具体例
フィボナッチ数列（前の2つの数字を足していく数列：1, 1, 2, 3, 5, 8...）の計算が有名です。単純にプログラムを作ると同じ項の計算を何度も繰り返してしまい処理が遅くなりますが、動的計画法では過去の計算結果を配列に保存（メモ化）して再利用します。
// 計算結果を保存する配列を用意し、再利用する
let memo = {};
function fibonacci(n) {
if (n <= 2) return 1;
if (memo[n]) return memo[n]; // すでに計算済みならその結果を返す
memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
return memo[n];
}
もう少し詳しく
動的計画法のアプローチには、大きく分けて二つの記述方法があります。一つ目は具体例に挙げたような「トップダウン方式（メモ化再帰）」です。これは、大きな問題からスタートして、必要になった小さな問題の計算結果をその都度メモリに書き込みながら進める手法です。二つ目は「ボトムアップ方式」で、一番小さな問題から順番に計算していき、その結果を表（配列）に順番に埋めていくことで、最終的に大きな問題の答えにたどり着く手法です。動的計画法が活躍する代表的な問題に「ナップサック問題」があります。これは、容量が決まっているリュックサックに、価値と重さが異なる複数の品物を、合計の価値が最大になるように詰め込む方法を考える問題です。このような、すべての組み合わせを計算すると膨大な時間がかかってしまう最適化問題において、動的計画法は部分的な最適解を表に記録しながら進めることで、現実的な時間で確実な正解を導き出すことができます。
試験でのポイント
情報処理技術者試験では、アルゴリズムの設計手法を問う問題の中で動的計画法が頻繁に取り上げられます。ポイントは、「部分問題の解を記録して再利用する」というキーワードを見逃さないことです。この特徴により、同じ計算を繰り返すことによる時間の無駄（計算量の爆発）を防ぐことができるというメリットを正確に理解しておきましょう。また、試験問題では、ナップサック問題や最短経路問題などを題材にして、計算過程の表の一部を埋めるような出題がされることもあります。動的計画法は、貪欲法のように「目先の最適」にとらわれることなく、常に「全体を通しての最適解」を確実に求めることができる手法であるという点も、他の手法との違いとして必ず押さえておくべきポイントです。
関連する用語
アルゴリズムの設計手法として頻出する貪欲法や分割統治法とは、問題へのアプローチ方法が異なるため比較できるようにしましょう。また、関数の処理効率を高めるメモ化の技術は、動的計画法のトップダウン方式に深く関わっています。