- Let \(0, 1\), and \(2\) represent colour red, green, and blue, respectively. Thus, we can use ternary to represent a row pattern. For instance, \(212_3 = 23_{10}\) represents the second layer from the given example.
- Then pre-compute all the valid rows by checking whether any two adjacent ternary digits in a number are the same. Hint: the \(n\)-th digit of a pattern is \(\lfloor pattern / 3^n\rfloor \bmod 3\)
- For each valid row pattern \(x\), pre-compute the set of all compatible next-row patterns \(y\) that satisfy the constraints between the two layers. This gives a transition list \(next[x]\), which tells us exactly which states can follow \(x\) in the DP.
- Finally, let \(dp[x]\) represents the number of valid colouring of all remaining lower layers, given that the current layer’s pattern is \(x\).
LeetCode 1931 is very similar to this problem.