给 N x 3 网格图涂色的方案数

/*
 * 思路：
 * 1. 每一行有3个格子，可以用3种颜色（红、黄、绿）进行上色，
 *    相邻格子的颜色必须不同。
 * 2. 第一行的12种可能性：ABA, ABC, ACB, BAC, BCA, BCB, CAB, CBA, CAC, CBC, CCB, CAC。
 * 3. 每行的状态可以分为两类：
 *    - type1：ABA 型，有6种可能性。
 *    - type2：ABC 型，有6种可能性。
 * 4. 通过递推关系，可以计算出第 n 行的方案数。
 * 5. 用动态规划 dp1 和 dp2 表示第 n 行分别为 type1 和 type2 的方案数。
 * 6. 初始值：dp1 = 6, dp2 = 6。
 * 7. 状态转移方程：
 *    - 新的 dp1 = 2 * dp1 + 2 * dp2
 *    - 新的 dp2 = 2 * dp1 + 3 * dp2
 * 8. 答案为 dp1 + dp2，对 10^9 + 7 取余。
 */
import java.util.stream.IntStream;
public class Solution {
    public int numOfWays(int n) {
        final int MOD = 1000000007;
        long[] dp = {6, 6};
        IntStream.range(1, n).forEach(i -> {
            long newDp1 = (2 * dp[0] + 2 * dp[1]) % MOD;
            long newDp2 = (2 * dp[0] + 3 * dp[1]) % MOD;
            dp[0] = newDp1;
            dp[1] = newDp2;
        });
        return (int) ((dp[0] + dp[1]) % MOD);
    }
}