動的計画法
またの名をDynamic Programming
組み合わせ最適化問題（あるN個の物からM個の組み合わせで最大値の物を探す、など）などで、計算量を減らすために使われる
組み合わせ最適化問題を単純に全探索で得と$ O(2^n)くらいの計算量がかかる
全ての物に対してあった場合/ない場合を考えるのを全ての組み合わせで行うため
これを動的計画法は$ O(NW)（ここで$ Nと$ Wはなんらかの組み合わせの数で、例えば商品数など）みたいに、 ある組み合わせの数 × 別のある組み合わせの数という、より少ない組み合わせ数に減らすための考え方
同じ計算をしている箇所をまとめあげて1回の計算に減らして、不必要な計算を減らす
具体的には、2個の組み合わせに対して行った最大値を、3個の組み合わせに対して行う最大値の計算に使うことで、再度2個の組み合わせに対して行う計算をしなくてよくする感じ
組み合わせ数 × 制約数ということも
制約数も組み合わせではある
ナップサック問題などに対する解法の一つ
メモ化再帰も実は動的計画法になる
メモ化によって以前の計算を使ってるよね
ある特定の問題をグラフの問題と捉え直して、あるパスからある後続のパスへの遷移による総和などを計算したりできる あるベクトル・行列（テーブル）を用意して、若いindexから順に探索して最大・最小を順次記録していく。
このテーブルの$ Nがある商品を選んだかどうか（緩和）の結果が格納されている
若いindexから順に値が確定して変更されないことが前提にある。
部分構造最適性 (optimal substructure)
そのため、後続のindexは、計算時に若いindexの値を用いて最大・最小を計算していく。
そうすることで、時間順などの系列データから最大・最小を計算できる。
現時点で考えられる最大値 or 最小値（ex. 現在入っている値）と、他のパス（ex. 前回の値 / N個前やテーブル上の同じ商品 / テーブル上の別の商品）からやってくる値の差を比較して、大きい方を採用するというイメージ
他のパスには複数の経路（ex. 前回の値 / N個前やテーブル上の同じ商品 / テーブル上の別の商品）が考えられることもあり、その時考えられる全てのパスごとに最大値計算を試して現在の値を更新していくと、最後に残ったやつがマジモンの最大値になるという風に考えられる
配る遷移形式
現在の最大値を、現在考えられている最大値 vs 今回の経路の最大値 + 今回得られるgainみたいに計算していく
貰う遷移形式
現在の最大値から、今回考るパスに対して、そのパスの現在の最大値 vs 最大値 + そのパスにいくことで得られるgainを比較して大きければ書き換える、みたいなことをやっていく