Leetcode-1411. 给 N x 3 网格图涂色的方案数-阿里3.6笔试题

1411. 给 N x 3 网格图涂色的方案数
你有一个 n x 3 的网格图 grid ，你需要用 红，黄，绿 三种颜色之一给每一个格子上色，且确保相邻格子颜色不同（也就是有相同水平边或者垂直边的格子颜色不同）。

给你网格图的行数 n 。

请你返回给 grid 涂色的方案数。由于答案可能会非常大，请你返回答案对 10^9 + 7 取余的结果。

解题思路
根据n=1的情况：可以将涂色情况分为ABA和ABC两种类型
其中可以推出：ABA的下一层为：BAB、BAC、BCB、CAC、CAB（三个ABA，二个ABC）
** ABC的下一层为：BAB、BCB、BCA、CAB（二个ABA，二个ABC）**

class Solution {
    private static final int MOD=1000000007;
    public int numOfWays(int n) {
        if(n==0) return 0;
        //n=1时的情况
        long ABA=6;
        long ABC=6;
        //ABA的下一层有3个ABA,两个ABC
        //ABC的下一层有2个ABA，两个ABC
        for(int i=2;i<=n;i++){
            ABC=((ABA+ABC)*2)%MOD;
            ABA=(ABC+ABA)%MOD;
        }
        return (int)((ABC+ABA)%MOD);
    }
}