DP状态设计

关于 DP 的技巧

0x01 状态与值域交换

DP 的状态可以和值域交换。
比如：dp[w]=v 表示选了前 \(i\) 个物品，背包容量为 \(w\) 的情况下可以装物品的最大价值为 \(v\)。
这就可以转换成 dp[v]=w 表示选了前 \(i\) 个物品，选的物品总价值为 \(v\) 时，可能的包包容量最小值为 \(v\)。
这样就可以解决一些状态存不下，但是值域比力小的标题。
这还可以用来节省维度，比如 dp 数组中存的是状态是否可行，值域是 \([0,1]\)，就可以把状态的此中一个维度移到值域上，节省一个维度。
AT_dp_e：一个 01 背包的板子，但是背包容量很大，物品的价值之和比力小，就可以采用上面的方法。
0x02 状态设计方法

DP 状态的设计可以先设计最暴力的状态（是最暴力的状态，不是暴力），然后看那些状态其实没有影响，那些状态是可以合并的。
AT_abc238_f：先设计出最暴力的状态，就是存一下前面所有没有选的人的两个排名，和当前选的 \(i\) 比力，如果两个排名都更小那么当前的 \(i\) 也不能选。考虑优化，其实有很多记载的人根本没有用上，我们只必要最小的。但是二维欠好比力大小，考虑按此中一维排序，再记载另一维的最小值。
CF1579G：先设计最暴力的状态：dp[L][R][pos] 表示选了前 \(i\) 个线段，最左端是 \(L\)，最右端是 \(R\)，当前端点是 \(pos\) 的情况是否可行。但是标题问的是左右端点之差，不必要得到确切的位置，只必要相对的位置。于是用 dp[l][r] 表示左端点 \(pos-l\)，右端点 \(pos+r\) 的情况是否可行，左右端点的差值就是 \(l+r\)。如今状态数降到了 \(nd^2\)，还是不行。这里 dp 维护的是可行性，就可以把此中一个维度移到值域，dp[l]=r 表示选了前 \(i\) 个线段，左端点是 \(pos-l\)，最小的右端点是 \(pos+r\)。
0x03 过去选择对如今选择无影响

如今的选择对答案的贡献与过去选择无关。
最简单的例子就是从一个有正有负的数列中选数使总和最大。上一个选没选对当前数对答案的贡献没有影响。
AT_dp_t[1]：对于一个字符串上的区间（两端都是问号或者字符串的端点此中之一），不论区间外面的字符怎么变，这个区间对答案的贡献都不会受到影响。dp 表示前 \(i\) 个字符的贡献之和，那么可以枚举 \(j(j==0\lor s_{j-1}=='>')\)，区间 \([j,i]\) 就可以构成一个全部  换成  段的长度加一的阶乘的倒数之积。但是每将一个 > 变成 ，求\(2^k\) 中变换方式的贡献之和。 ↩︎
</ol>