動的計画法のアルゴリズム

動的計画法アルゴリズムは以下の通り。

  1. 最適解の構造を特徴づける
  2. 最適解の値を再帰的に定義する
  3. ボトムアップに最適解の値を求める
  4. 最適解を構成する

1.最適解の構造を特徴づける

問題がより小さい問題に分けることができ、問題の最適解に小さく分けた問題(部分問題)の最適解が含まれる場合は動的計画法により解くことができる。(部分問題最適性)

2.最適解の値を再帰的に定義する

n番目の値を求めたい。n-1番目の値を求める必要がある。

n-1番目の値を求めたい。n-2番目の値を求める必要がある。

n-2番目の値を求めたい。n-3番目の値を求める必要がある。

・・・

2番目の値を求めたい。1番目の値を求める必要がある。

1番目の値を求めたい。

上記のように再帰的に最適解の値を定義する。

3.ボトムアップに最適解を求める

最適解の値は再帰的に定義されるため、

1番目の値を決める。

2番目の値が決まる。

3番目の値が決まる。

・・・

n-1番目の値が決まる。

n番目の値が決まる。

というように最初の値を決めることでボトムアップ的に最適解が求められる。

4.最適解を構成する

どのルートを辿ってきたかを記録しておき、逆順にたどることで最適解の構成がわかる。