動的計画法

解決するべき問題を簡単に解決できる細かい問題に分割し、その細かい問題の解答を利用して大きな問題を解くこと。

動的計画法に向いている問題

再帰的な問題は向いている。また最適部分構造(親問題が最適化を問うており、その子問題も同様に最適化を問うている)を持っている問題も向いている。

動的計画法には大きく分けて「タビュレーション」と「メモ化」という2つのアプローチがある。

タビュレーションとは「表」を表す。つまり計算結果を表に保管しておき、それをキャッシュとして参照し重複した計算を減らすというもの。計算を行う順序はベースケース（ex. n=0）→目的のケース（ex. n=100）のようにボトムアップ方式で行う。

例えば再帰的なアルゴリズムを想定する。f(n)を求める場合にf(n-1)が必要とすると、タビュレーションにおける計算順序は f(0)→f(1)→...→f(n)となる。

基本的な考えはタビュレーションと同様で、計算結果をキャッシュする。異なるのは計算順序。

タビュレーションがボトムアップであったのに対してメモ化はトップダウン。つまり上記例だとnが大きいものからキャッシュされているかを確認し、キャッシュされていない場合はそれを計算して結果をキャッシュに保存するというもの。

全ての下位問題（上記例の場合n=0など）を解く必要がある場合はタビュレーションの方が優れている。再帰関数をスタックに保存する手間が省けるからである。

一方全ての下位問題を解く必要がない場合はメモ化の方が良い。最終的な解を求めるために必要な処理のみを行うからである。