動的計画法
動的計画法とは
直接計算すると大きな時間がかかってしまう問題に対し、途中の計算結果をうまく再利用することで計算効率を上げる手法のこと。
下記2条件を満たすアルゴリズムの総称。
分割統治法:部分問題を解き、その結果を利用して全体問題を解く
ボトムアップ
メモ化:部分問題の計算結果を再利用する
同じ計算を行わないということ
トップダウン
メモ化(トップダウン)
分割統治法・漸化式ループ(ボトムアップ)
https://gyazo.com/ae3e23ea3594ddd056306746dff4663e
トップダウン => 上の図で7から計算して枝に移っていく
ボトムアップ => 上の図で 1 から計算していく
問題例