動的計画法のアプローチには、大きく分けて二つの記述方法があります。一つ目は具体例に挙げたような「トップダウン方式（メモ化再帰）」です。これは、大きな問題からスタートして、必要になった小さな問題の計算結果をその都度メモリに書き込みながら進める手法です。二つ目は「ボトムアップ方式」で、一番小さな問題から順番に計算していき、その結果を表（配列）に順番に埋めていくことで、最終的に大きな問題の答えにたどり着く手法です。動的計画法が活躍する代表的な問題に「ナップサック問題」があります。これは、容量が決まっているリュックサックに、価値と重さが異なる複数の品物を、合計の価値が最大になるように詰め込む方法を考える問題です。このような、すべての組み合わせを計算すると膨大な時間がかかってしまう最適化問題において、動的計画法は部分的な最適解を表に記録しながら進めることで、現実的な時間で確実な正解を導き出すことができます。
情報処理技術者試験では、アルゴリズムの設計手法を問う問題の中で動的計画法が頻繁に取り上げられます。ポイントは、「部分問題の解を記録して再利用する」というキーワードを見逃さないことです。この特徴により、同じ計算を繰り返すことによる時間の無駄（計算量の爆発）を防ぐことができるというメリットを正確に理解しておきましょう。また、試験問題では、ナップサック問題や最短経路問題などを題材にして、計算過程の表の一部を埋めるような出題がされることもあります。動的計画法は、貪欲法のように「目先の最適」にとらわれることなく、常に「全体を通しての最適解」を確実に求めることができる手法であるという点も、他の手法との違いとして必ず押さえておくべきポイントです。
アルゴリズムの設計手法として頻出する貪欲法や分割統治法とは、問題へのアプローチ方法が異なるため比較できるようにしましょう。また、関数の処理効率を高めるメモ化の技術は、動的計画法のトップダウン方式に深く関わっています。