1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int numOfWays(int n) {
        long allDiff = 6, alternate = 6, modulo = (long) 1e9 + 7;
        for (int i = 1; i < n; i++) {
            long nextAllDiff = allDiff * 3 + alternate * 2;
            long nextAlternate = allDiff * 2 + alternate * 2;
            allDiff = nextAllDiff % modulo;
            alternate = nextAlternate % modulo;
        }
        return (int) ((allDiff + alternate) % modulo);
    }
}

如果是1行. 可以分类讨论一下:
121情况: 121, 131, 212, 232, 313, 323
123情况: 123, 132, 213, 232, 312, 321
每个都是六种.

那么第二行121和123的情况各是多少种呢?
假设第一行是个121的情况, 比如是131. 那下一行:
121情况: 212, 313, 323.
123情况: 213, 312.
假设第一行是123的情况, 比如是132. 那下一行:
121情况: 212, 232.
123情况: 213, 321.

因此如果第一行是121类型的, 那下一行会有3个121pattern的, 2个123pattern的.
如果第一行是123类型的, 下一行会有2个121pattern的, 2个123pattern的.

因此第n行121pattern的个数为上一行121pattern的个数 * 3 + 上一行123pattern的个数 * 2.
第n行123pattern的个数为上一行121pattern的个数 * 2 + 上一行123pattern的个数 * 2.

最后我们得到最终结果后把121pattern的个数和123pattern个数加在一起就可以了.

时间复杂度: O(n)
空间复杂度: O(1)