DPに強くなるために集めたまとまりのない知見メモ
代数学的アプローチ
- 部分解同士の結合演算に対して可換モノイドである必要がある
- ほとんどの場合問題の定義によって一意に決まる
- だいたい総和(+)、min、maxのどれかに収まる
- 性質上Segment Treeと非常に相性が良い。DP表の横軸を遅延セグ木に置き換えると強い。
- 部分解同士の結合演算を $\oplus$ 、部分解と中間要素の結合演算を $\odot$ と置いた場合、 $(a \odot c) \oplus (b \odot c) = (a \oplus b) \odot c$ を満たす。
- 意外と重要
- $\odot$ は交換法則および結合法則を満たさない。しばしば単なる代入演算だったりする1
上記の条件を満たす演算を半環というらしい。
プログラム記法的アプローチ
- 論理的にはメモ化再帰と同じ
- 再帰関数と遅延評価を使ったHaskellでの実装例がある
圏論的アプローチ
- 圏論上の用語ではDynamorphismというらしい
- 詳細は省く（そもそもよく分かってない）が、途中の部分解を保持する再帰的計算構造を構築する概念
- foldとunfoldの組み合わせのようにみなされる
- Recursion Treeの構築と収斂に分割できる
- Anamorphism + histomorphism
- 米田の原理
- いわゆるカリー化
- 式そのものの構造を扱いたい訳ではないのでそんなに重要ではないかも
- 半環は可換モノイド上の自己準同型写像…というもので表現できるらしい。
- なんもわからん
参考文献
メインコンテンツ
-
$a \odot b = a$ ↩