動的計画法
以下の2種類の実現方法がある。
履歴管理を用いるトップダウン方式(英: top-down with memoization) - 分割統治法において、計算結果を記録(メモ化)して再利用する方法。再帰を併用する場合はメモ化再帰(英: memoized recursion)とも呼ばれる。
ボトムアップ方式(英: bottom-up method) - 先に部分問題を解いていく方法
初歩的な説明で使われるフィボナッチ数の計算、ハノイの塔の必要移動回数の計算などでは、一次元の表(列)によって指数オーダーの計算時間を入力の数の大きさに対して線形時間に落とすことができる。(ただし、これらの級数の計算では、漸化式で参照するのは高々 2 つ前の計算結果だけなので、変数を1, 2 個用意してループすればことたりる。)効果が顕著なのが組合せ問題で、文字列の近似照合(編集距離の計算)、ナップサック問題の解法などが、二次元の表により指数時間の手続きが多項式時間に効率化される有名な例である。マルチプルアラインメントのように表が三次元以上必要になると、時間に対するトレードオフとなるメモリ領域量が大きくなりすぎるため、規模の大きな入力には実用的でなくなる。
近似アルゴリズムの分野では、多項式時間での解法が存在しないと思われる一部の問題に対して、この方法を適用することで、擬似多項式時間では最適解を得ることができる。