记 \(f[i][j]\) 表示把 \(s[i \sim j]\) 变成回文，最少补几个，从 \(f[i][j - 1], f[i + 1][j], f[i + 1][j - 1]\) 三种情况转移过来即可。感性理解一下这样的状态定义是有最优子结构的。
肯定可以区间 \(dp\)，再注意到状态的转移和上一步有关，所以记 \(f[i][j][0/1]\) 表示 \(H[i \sim j]\) 的方案数，其中 \(0\) 表示最新的一个人插进了队形左端（即 \(H[i]\)），\(1\) 就是右端（即 \(H[j]\)），根据大小关系转移即可。
唯一值得注意的是此题可以倒推，并且倒推之后的答案统计是 \(O(1)\) 的。正推的答案统计是 \(O(n)\) 的。
一个很朴素的想法是把两条路的位置同时都实时记录下来，这样就好转移了，事实证明是可以的。
记 \(f[i][j][p][q]\) 表示第一条路走到了 \((i, j)\)，第二条路走到了 \((p, q)\) 的最大权值和。它可以转移到四种情况，即：
- 第一条路 往右走， 第二条路 往右走。
- 第一条路 往右走， 第二条路 往下走。
- 第一条路 往下走， 第二条路 往右走。
- 第一条路 往下走， 第二条路 往下走。
分 点重合/不重合 两种情况赋予转移代价，套上 \(BFS\)， 直接转移就是 \(O(n^4)\) 的，当然需要标记一下每个点是否访问过。
考虑优化成 \(O(n^3)\)，注意上面的方法两条路走的步数始终相同。记 \(f[i][j][k]\) 表示两条路都走了 \(i\) 步，第一条路处于第 \(j\) 行，第二条路处于第 \(k\) 行，最大权值和。起点是 \((1, 1)\)，因此 \((x - 1) + (y - 1) = i\)， 则 \(y = i - x + 2\)。最后特判一下只走了 \(1\) 步的情况就行，因为不满足这个式子。
学到一个 \(trick\) : 区间相关的环形问题，可以把序列复制一遍接在后面，然后只推到 \(len = n\) 就可以了，最后取 \(\max_{i \in (1, n + 1)} f[i][i + n - 1]\)。这样比 \(n\) 次区间 \(dp\) 快很多，因为不同的断点位置下的区间可以使用相同的一段很小的区间。
最大子段和 + 前后缀max 连一下就可以。
一个最大独立集问题，记 \(f[u][0/1]\) 表示选 \(u\) 或者不选 \(u\)，对于一个儿子 \(v\)，有转移：
\[f[u][0] = \sum\min(f[v][0], f[v][1]) \]\[f[u][1] = \sum[v][0] + val[u] \]树上背包，记得给 \((u, v)\) 留一条边就可以了，并且一定要连这条边，不然转移没有意义。
只有 \(n\) 能进行状态压缩。一开始的想法是记 \(f[i][S]\) 表示前 \(i\) 个操作，强制选 \(i\)，然后得到了 \(S\) 这个集合，最少操作数。然后还“机智”地发现开个 \(vector[i]\) 表示 \(f[i][?]\) 有哪些更新出来了。
然而无济于事，因为此题 \(dp\) 的顺序并不是简单的递推（会有后效性），因此采用记忆化 \(BFS\) 进行实现。
答案： \(min(f[i][0])\)。
初始化： \(f[0][(1 << n) - 1] = 0\)，其他初始化为 \(inf\)。
式子就是 \(f[i][S] = min(f[j][T] + 1, f[i][S])\)， \(T\) 的话就照着题目要求根据 \(S\) 推出来。
时间复杂度为 \(O(2^nmn)\)。
最后发现其实当前具体在哪个操作并不重要（下一步转移都是向全部操作），所以可以优化成一维。并且由于广搜良好的性质找到一个 \(f[0]\) 就直接输出就可以！
状态压缩DP技巧 - A Simple Task 「CF11D」
一开始想成树形dp了，然后发现非常的难写，因为点之间有各种路径计数，很难补充不漏。每次扩展和前一个状态的联系也不是很大。
题解是一种巧妙的状压dp。显然可以对已选点集进行状压。先考虑如何统计环的数量，对于 \(i \to j\) 的一条简单路径，若路径外一点 \(k\) 同时和 \(i\)，\(j\) 有连边，那么就成了一个环。基于此，我们可以转化成利用 \(dp\) 统计简单路径的数量，而统计答案时在另找一个点连环。（状压没想到，但这一步转化想到了……）
这样定义出来的状态是 \(f[S][i][j]\)，表示选择的点集为 \(S\)， \(i \to j\) 的简单路径的数量。转移比较好写。空间复杂度会达到 \(2^{19} \times 19^2 = 189,267,968\)，存不下，时间应该还要再乘一个 \(19\)， 也爆掉了。
考虑怎么优化时空。注意到后两维其实都是我们主动加的限制，但仅仅是为了统计答案而同时维护这两维显得有些不划算。能不能利用好 \(S\) 中包含 \(i, j\) 的性质进行一些优化呢？
考虑强制规定 \(lowbit(S)\) 那一位是起点，\(i\) 作为终点，这样只要遇到一个满足 \((1 << i) = lowbit(S)\) 的 \(i\)， 就统计答案。
状态： \(f[S][i]\)，意义如上。
答案： \(ans = \sum_{lowbit(S) = 2^i}f[S][i]\)。最后记得 \(ans = (ans - m)/2\)， 因为会误算 一条边和两个端点的“假环”。
初始化： \(f[2^i][i] = 1,i \in [0, n - 1]\)。
转移：
\[\begin{align}ans &+= f[S][i] &\text{lowbit(S) = (1 << j)} \\f[S | (1 << j)][j] & += f[S][i] & \text{lowbit(S) < (1 << j)}\end{align} \] 标签：20241016,清理,第一条,DP,ans,第二条,模板,转移,dp From： https://www.cnblogs.com/superl61/p/18471008