Number of Ways to Paint N x 3 Grid

This problem can be modelled as a graph traversal problem. Each of the 12 valid colorings of a single row can be represented as a node in a graph. There exists a directed edge from node A to node B if coloring B can be placed on top of coloring A. Specifically, the states are numbered in the order they were provided in the example. I then wrote a script to generate the adjacency list. (omitted)

We can then use dynamic programming to count the number of ways to reach each node after n steps. In particular, $dp[i][j]$ represents the number of ways to reach node $j$ after $i$ steps. We can then transition from $dp[i][j]$ to $dp[i+1][k]$ for each neighbor $k$ of $j$. The base case is $dp[0][j] = 1$ for all $j$, as there is one way to start at each node. In the code below, an optimization is made to only store the previous row of the dp table, as only that is needed to compute the next row.