Readme

1931.Painting-a-Grid-With-Three-Different-Colors

观察到行数m不超过5，我们就可以考虑以每一列整体作为状态进行动态规划。每一列的状态数是3^m不超过243，其中符合条件（相邻不同色）的状态会更少,m等于5时也只有48。我们可以用一个不大的三进制整数来表示每个格子的喷涂选择。比如三进制01210就表示一列里五个格子的颜色。

我们考虑第i列的某个状态s时，唯一的制约因素就是第i-1的状态。我们遍历第i-1列的状态的所有可能t，注意查看是否s和t是否符合并存的条件（即相邻不同色），然后累加dp[s]+=dp[t].

极限数据情况下的时间复杂度大概是48*48*1000=2e6，时间复杂度可以接受。