复制粘贴的：
通过一个外层的 DP 来计算使得另一个 DP 方程最终结果为特定值的输入数。
例如求有多少种输入使得一个背包 DP 恰好答案为 \(K\)。
外层 DP 的状态是所有子 DP 的状态的值。
子 DP 状态数很少，通常经过滚动数组优化，比如 \(3n\) 变成 \(2\times 3\)）
通常我们有技巧地枚举子 DP 的输入，比如逐位考虑输入。
由于我们只对 DP 方程的最终结果感兴趣，我们并不需要记录子 DP 的输入数据，只需要记录转移以后，DP 每个状态的值就可以了。
例：BZOJ3864
题目大意：
给定字符串 \(S\) 与正整数 \(m\)，你需要对每个 \(i=0,\cdots,|S|\) 求出：
- 有多少个长为 \(m\) 的字符串 \(T\) 使得 \(\text{LCS}(S,T)\) 长度为 \(i\)。\(\text{LCS}\) 指最长公共子序列。
\(1\le m\le 1000,1\le |S|\le 15\)。
回忆 \(\text{LCS}\) 的 DP： \(f(i,j)\) 表示 \(S[1\cdots i],T[1\cdots j]\) 的 LCS 长度，有转移：
\[f(i,j)=\begin{cases}f(i-1,j-1)+1&,S[i]=T[j]\\\max(f(i-1,j),f(i,j-1))&,S[i]\neq T[j]\end{cases} \]我们应当记录的是，目前长度为 \(i\)，且和 \(S\) 的 LCS 是某个数组的字符串数量。
注意到这个转移之和上一行相关，因此只需要记录最后一行，即对每个 \(f(\cdot,j)\) 的所有状态，都记录下来。暴力记录需要 \(O(|S|^{|S|})\) 个状态，注意到差分数组只会是 \(0,1\)，因此考虑记录差分数组，即可做到 \(O(2^{|S|})\)。用 \(O(|\Sigma|\times |S|2^{|S|})\) 时间预处理所有状态的后继，总的时间复杂度为 \(O((m+|S|)2^{|S|}\times |\Sigma|)\)。
- 附送简单题 游园会，记录末尾是不是 N,NO 即可。
试看看！
我觉得大标题后紧跟小标题很不好看，因此我要在这里加一行字。
優しさの記憶
dp of dp 套一层数位 DP。不难想到枚举 \(i=1,\cdots,n\) 算贡献。
考虑怎么算最长公共子串，设 \(f(i,j)\) 表示两个串 \(s,t\) 以 \(s_i,t_j\) 结尾的最长公共子串，那么
\[f(i,j)=\begin{cases}f(i-1,j-1)+1&,s_i=t_j\\0&,s_i\neq t_j\end{cases} \]我曾一度以为状态数应当是 \(5^4=625\)，但注意到 \(f(i,j)\le \min(i,j)\)，因此状态数不超过 \(2\times 3\times 4\times 5=120\)。由于这个只代表某两个位置结尾的最长公共子串，还要记录全局 \(f\) 的最大值。
额，但是算出来是 \(n\times \lg m\times |\Sigma|\times \lg n\times 120\times 2\times 2\times\ge 4\times 10^9\)，有点恐怖！不过 CYJ 说能过
另一种做法：枚举之后把每个后缀插入 acam，标记一下每个点在 trie 上的深度，记录一下当前走过路径上的 maxdep 即可。复杂度是 \(O(n|\Sigma|\lg n\lg m)\)。
輪廻
额我也不知道这题算不算 dp of dp
不难发现剩下的数必然是 \(n\)，考虑对一个排列怎么算次数：建出笛卡尔树，发现只要一个节点的左子树或者右子树被删空了，那么它就会被删除。在笛卡尔树上 DP，设 \(f_u\) 表示删空 \(u\) 子树需要的次数，则当 \(u\) 不在左右边缘时 \(f_u=\max(f_{\text{lson}(u)},f_{\text{rson}(u)},\min(f_{\text{lson}(u)},f_{\text{rson}(u)})+1)\)，否则 \(f_u=f_{\text{lson/rson}(u)}+1\)。
现在要计数有多少个排列的笛卡尔树能够使得 \(f_{\text{root}}=k\)。发现 \(f\) 的转移式中 \(\max\) 取到第三种情况当且仅当 \(f_{\text{lson}(u)}=f_{\text{rson}(u)}\)，因此设 \(F(i,j)\) 表示 \(1\cdots i\) 的排列，最终 \(f_{\text{root}}=j\) 的方案数；转移时枚举最大值的位置，有
\[F(x,j_0)\times F(y,j_1)\times\binom{x+y+1}{x}\to F(x+y+1,\max(j_0,j_1,\min(j_0,j_1)+1)) \]然后是一个很厉害的结论，注意到删除次数不超过 \(O(\log n)\)（由于一个序列至多有一半的数是极大值），因此暴力转移就是 \(O(n^2\log ^2n)\)，前缀和优化一下可以 \(O(n^2\log n)\)。
由于 \(u\) 在最左侧时转移式不同，因此需要多记录 \(G(i,j)\) 表示 \(i\) 在最左侧的方案数。
LOJ3724
有个暴力：\(f(u,x,y)\) 表示给以 \(u\) 为根的子树填数，选 \(u\) 时的最大权独立集大小为 \(x\)，不选 \(u\) 时为 \(y\) 的方案数。转移就直接写一下树上最大权独立集那个 DP，有
\[f(u,x_1,y_1)\times f(v,x_2,y_2)\to f(u,x_1+y_2,y_1+\max(x_2,y_2)) \]发现复杂度是 \(O(n^3k^4)\)。
然后发现，当 \(x\le y\) 的时候记录 \(x\) 没有意义，若 \(x>y\)，那么 \(x-y\le k\)。因此可以记录 \(f(u,j,y)\) 表示以 \(u\) 为根的子树填数，选 \(u\) 时的最大权独立集大小为 \(y+j\)（\(j>0\)） 或者 \(\le j\)（\(j=0\)），不选 \(u\) 时为 \(y\) 的方案数。转移式类似：
\[f(u,j_1,y_1)\times f(v,j_2,y_2)\to f(u,\max(0,j_1-j_2),y_1+y_2+j_2) \]复杂度 \(O(n^2k^4)\)。
标签：max,le,记录,text,times,理解,简单,DP From： https://www.cnblogs.com/YunQianQwQ/p/17277140.html