以下に、ダイナミックプログラミングの基本的な考え方と、具体的なコード例を示します。
- メモ化再帰法: メモ化再帰法は、再帰的な呼び出しを行いながら、計算結果を保存して再利用する手法です。この手法を使用すると、同じ引数に対する再帰呼び出しを複数回行う必要がなくなり、計算量を削減できます。
例えば、フィボナッチ数列を求める問題を考えてみましょう。通常の再帰的な解法では、同じ数に対する計算が重複するため、指数時間がかかります。しかし、メモ化再帰法を使用すると、計算結果を保存して再利用することで、線形時間で解を得ることができます。
- ボトムアップ法: ボトムアップ法は、再帰的な呼び出しを使わずに、小さな部分問題から順に解を求めていく手法です。この手法では、部分問題の解を表すためのテーブルを作成し、それを用いて上位の問題の解を計算します。
例えば、最長増加部分列 (Longest Increasing Subsequence) を求める問題を考えてみましょう。通常の再帰的な解法では、指数時間がかかります。しかし、ボトムアップ法を使用すると、部分問題の解を保存しながら順に解を計算することで、線形時間で解を得ることができます。