易证, 所有只有一边染色的（即题解中所说的[1][0], [2][0], [0][1], [0][2]）的dp值必然相同

所有两边都染色的（即题解中所说的[1][1], [1][2], [2][1], [2][2]）的dp值也必然相同

那么三个状态就够了呢

/**
 * 0: Not-colored
 * 1: OneSide-colored
 * 2: Both-colored
 */
int64 f[N][N][3];

我的全部代码可以见 CF submission #105970405

其中 ok[i][j] 表示 i~j 是否为一个合法的括号序列

回复我的话记得at一下谢谢呢