動的計画法
リファレンス
DPを構成する要素は主に３つ。
DPテーブルの形
遷移の仕方
テーブルに入る値
計算量はだいたいDPテーブルのサイズ＊１要素あたりの遷移数
DPテーブルの形による分類
$ n次元DP
遷移の仕方による分類
テーブルに入る値による分類
さまざまなテク
状態のまとめ方に関するテク
特殊な添字を用いる
構築途中の数字列がある値を超えるかをboolで持つ
最後に訪問した頂点を添え字に持つ
キーと値を入れ替える
DPテーブル内に持つ値の上限が小さい場合、そちらを添字にすることでDPテーブルのサイズを抑えられる。
ある値を超えるために必要な最小コストを求める問題などで、目的の値を超える部分はまとめて考える。
高速化のテク
DPテーブルの次元を減らす
DPテーブルの更新で直前の行しか参照しない場合、テーブルをすべて持たずに直前の行だけを保存する。オーダーレベルの計算量改善ではないがかなり速くなる。
DPテーブルとは別にそれまでに確定した値の累積和をメモする。区間和を求める遷移を$ O(1)で処理できる。
同じ配列を使いまわすことで更新しない部分をそのままにしておける。メモリの節約にもなる。逆側から更新していくことで同じ要素を$ 2回以上使わないようにする。
区間最小などを用いて遷移するDPではセグメント木に値を乗せることで遷移を高速化できる。 DPを用いる有名問題