DP状态设计

关于 DP 的技巧

0x01 状态与值域交换

DP 的状态可以和值域交换。

比如：dp[i][w]=v 表示选了前 \(i\) 个物品，背包容量为 \(w\) 的情况下可以装物品的最大价值为 \(v\)。

这就可以转换成 dp[i][v]=w 表示选了前 \(i\) 个物品，选的物品总价值为 \(v\) 时，可能的包包容量最小值为 \(v\)。

这样就可以解决一些状态存不下，但是值域比较小的题目。

这还可以用来节省维度，比如 dp 数组中存的是状态是否可行，值域是 \([0,1]\)，就可以把状态的其中一个维度移到值域上，节省一个维度。
AT_dp_e：一个 01 背包的板子，但是背包容量很大，物品的价值之和比较小，就可以采用上面的方法。

0x02 状态设计方法

DP 状态的设计可以先设计最暴力的状态（是最暴力的状态，不是暴力），然后看那些状态其实没有影响，那些状态是可以合并的。

AT_abc238_f：先设计出最暴力的状态，就是存一下前面所有没有选的人的两个排名，和当前选的 \(i\) 比较，如果两个排名都更小那么当前的 \(i\) 也不能选。考虑优化，其实有很多记录的人根本没有用上，我们只需要最小的。但是二维不好比较大小，考虑按其中一维排序，再记录另一维的最小值。

CF1579G：先设计最暴力的状态：dp[i][L][R][pos] 表示选了前 \(i\) 个线段，最左端是 \(L\)，最右端是 \(R\)，当前端点是 \(pos\) 的情况是否可行。但是题目问的是左右端点之差，不需要得到确切的位置，只需要相对的位置。于是用 dp[i][l][r] 表示左端点 \(pos-l\)，右端点 \(pos+r\) 的情况是否可行，左右端点的差值就是 \(l+r\)。现在状态数降到了 \(nd^2\)，还是不行。这里 dp 维护的是可行性，就可以把其中一个维度移到值域，dp[i][l]=r 表示选了前 \(i\) 个线段，左端点是 \(pos-l\)，最小的右端点是 \(pos+r\)。

0x03 过去选择对现在选择无影响

现在的选择对答案的贡献与过去选择无关。

最简单的例子就是从一个有正有负的数列中选数使总和最大。上一个选没选对当前数对答案的贡献没有影响。

AT_dp_t^[1]：对于一个字符串上的区间（两端都是问号或者字符串的端点其中之一），不论区间外面的字符怎么变，这个区间对答案的贡献都不会受到影响。dp[i] 表示前 \(i\) 个字符的贡献之和，那么可以枚举 \(j(j==0\lor s_{j-1}=='>')\)，区间 \([j,i]\) 就可以组成一个全部 < 的区间。至于 \([1,j-1]\) 的选择是什么跟现在区间的贡献完全没有关系，乘上现在区间的贡献就行了。

0x04 错算

DP 过程中有一些算出来的答案过大/过小/不符合状态定义，但是最终的答案是对的。

P3959：dp[dep][s] 表示已经加入了树上的深度前 \(dep\) 层，加入点的状态为 \(s\) 的最小代价。

但是一个点可能有深度比计算的更小的情况，有一些状态的答案会算大，但是最终总会算到正确的那一个，对答案没有影响。

其实我觉的这有一点像 P14362，枚举到的中转点可能不会用，导致当时的答案偏大，但是最终会枚举到不用这个中转点的情况，还是能算出正确答案。

---

1. 转化后的题意：一个字符串中有两种字符 < 和 >，需要将 > 换成 < 或 ?，对答案的贡献是所有连续的 > 段的长度加一的阶乘的倒数之积。但是每将一个 > 变成 < 答案就要乘上 -1。字符串中一共有 \(k\) 个 >，求\(2^k\) 中变换方式的贡献之和。 ↩︎