dp过程中处理不合法的状态有两种方法:
1.防止不合法的状态进行转移(一般用于考虑一个状态能够转移到哪些状态, 因为可以一次性判断)
2.防止转移过去的状态不合法(一般用于考虑一个状态能够通过哪些子状态得到, 同样可以一次性判断)
当防止不合法的状态进行转移 => 不合法状态是存在合法值的
防止转移过去的状态不合法 => 不合法的状态的值永远都是不合法(取决于初始化)
因为大部分的题目都无法保证进行转移的状态是否合法, 所以初始化不合法的状态为一个不合法的值, 那么就算转移过去, 那么状态的值也是不合法的
例如该题(小国王)
一开始仅仅初始化 $f[0][0][0] = 1$ 为合法状态, 其他等于 0, 那么在后面状态转移的过程中,
如果是不合法的状态转移过去, 恒为$0$, 并不会影响答案(方案数)的正确性
大部分求最小值 / 最大值的题目都要将所有不合法的状态初始化为 正无穷 / 负无穷, 就是为了让不合法的状态进行转移也不会影响答案的正确性
(玉米田)
不需要考虑 上一行 的状态是否合法(即有没有种到不育的地上), 不合法状态的值一定 == 0, 进行累加不影响答案的正确性
又例如该题(炮兵布阵)
1. 在判断与$g$的合法性中, 只需要判断$a$状态与$b$状态, 不需要判断$c$状态, 因为$c$状态不属于$i$阶段, 它的所有最值已经在$i-1$阶段中计算出来了, 如果不合法, 那么它的值也一定不合法
2. 同理, 在判断 (a & b) | (a & c) | (b & c) 中, 这个(b & c)可以省略的, 如果它的结果 != 0, 那么$f[i-1][b][c]$的状态的值一定不合法
(数字三角形)
一开始初始化所有的值为 负无穷, 就是防止所有不合法的状态更新合法的状态
因为无法保证进行转移用到的状态都是合法的(否则要加许多特判)