動的計画法
#アルゴリズム
Dynamic Programming, DP
大きな問題を複数の部分問題に分割し、部分問題の結果を記録しながら解いていく手法
以下の2種類の手法が存在する
トップダウン式
部分問題を逐次解いていきメモ化する手法
分割統治法
再帰の場合、メモ化再帰となる
ボトムアップ式
先に部分問題を解いておく
動的計画法が適用できる問題の例
フィボナッチ数
ハノイの塔