插入 dp

简介

一般问题为：考虑一个元素插入在其它元素的前 / 后。

状态设计一般为 \(dp_{i, j}\) 表示前 \(i\) 为且第 \(i\) 位排名为 \(j\) 的方案数。

例题

AT_dp_t Permutation

插入 dp 板子。

AT_abc209_f [ABC209F] Deforestation

邻项交换贪心钦定大小关系然后 dp。

AT_abc267_g [ABC267G] Increasing K Times

与原序列相对顺序无关，排序。对于前 \(i - 1\) 个位置可以有 \(i\) 个位置插，对于答案对数的变与不变转移即可。