此题和1349.Maximum Students Taking Exam很相似。第i行的喷涂方法只受第i-1行喷涂方法的约束。所以是第I类基本型的DP问题。
考虑到每一行的喷涂方法就只有3^3=27种，是可以枚举过来的。我们可以利用状态压缩的思想，用一个小于27的整数来代表一种喷涂方法。
我们定义dp[i][p]表示当第i行喷涂p方案时，前i行整体的喷涂方案总数。于是
dp[i][p] = sum(dp[i-1][q])
其中q就是第i-1行的喷涂方案，要求q与p不冲突，且q和p都是合法的。
最终的答案是最后一行所有合法喷涂方案p对应的dp值的总和。
另外一种解法就要费神一些。设计状态color2表示第i行喷涂两种颜色时（整体）的方案总数；color3表示第i行喷涂三种颜色时（整体）的方案总数。
假设某一行喷涂两种颜色，可以用ABA表示。那么如果下一行也是喷涂两种颜色，只可能是如下模式：BAB, BCB, CAC. 如果下一行喷涂三种颜色，只可能是如下模式：BAC, CAB.
假设某一行喷涂三种颜色，可以用ABC表示。那么如果下一行也是喷涂两种颜色，只可能是如下模式：BAB, BAB. 如果下一行喷涂三种颜色，只可能是如下模式：BCA, CAB.
于是我们可以得到行与行之间的状态转移方程：
color2 = 3*color2' + 2*color3'
color3 = 2*color2' + 2*color3'