問題のネタバレを多く含みます 挿入 DP 隣り合う項の大小関係に条件がついた順列を数え上げるときに使われることが多い。 $\mathrm{dp}(i, S) := $ $(1, 2, \dots, i$ からなる順列のうち、$S$ をみたすものの個数$)$ という状態を考えるのだが、遷移の考え方によって二種類の型に分けられる(と考えている)ので、それぞれについて説明する。 その①「割り込み」型 前から作っていくのではなく、遷移の際に「$1, 2, \dots, i - 1$ からなる順列のどこに $i$ を挿入するか」を考える。 DEGwer さんの数え上げ PDF で紹介されているのはこっち…