给 N x 3 网格图涂色的方案数[动态规划]

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

给你网格图的行数 n 。

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

示例 1：
输入：n = 1
输出：12
解释：总共有 12 种可行的方法：

分析：分别用A, B, C表示红，黄，绿三种颜色中的任意一种；则每一行的排列方式可以使ABA或ABC;<br />    (1)、如果第i行的排列方式ABA，那么其下一行满足要求的排列方式为：[BAB, BCB, CAC], {BAC, CAB}<br />    (2)、如果第i行的排列方式ABC, 那么其下一行满足要求的排列方式为: [BAB, BCB], {BCA, CAB}<br />    其中：[]表示的依旧是ABA的排列方式，{}中表示的是ABC的排列方式；
回到题目：第i+1行的涂色方案数只与第i行的涂色方案排列方式有关；<br />    所以可以采用动态规划的方式来解决这个问题：由于第i行有两种不同的排列方式(ABA和ABC方式)；<br />    所以定义一个dp[n][2]的状态数组：<br />    其中：dp[i][0]表示第i行按照ABA方式排列的方案数；dp[i][1]表示第i行按照ABC方式排列的方案数<br />    状态转移：<br />            dp[i+1][0] = 3*dp[i][0] + 2*dp[i][1];<br />            dp[i+1][1] = 2*dp[i][0] + 2*dp[i][1];<br />    状态初始化：dp[0][0] = 6, dp[0][1] = 6;
最后的结果为： dp[n-1][0] + dp[n-1][1];

int numOfWays(int n) 
{
    typedef unsigned long long ULL;
    ULL MAX_NUM = 1000000007;
    // dp initialize
    ULL dp_i_0 = 6;
    ULL dp_i_1 = 6;

    for(int i=1; i<n; ++i){
        ULL new_dp_i_0 = (3 * dp_i_0 + 2 * dp_i_1) % MAX_NUM;
        ULL new_dp_i_1 = (2 * dp_i_0 + 2 * dp_i_1) % MAX_NUM;

        // update dp_i_0 and dp_i_1
        dp_i_0 = new_dp_i_0;
        dp_i_1 = new_dp_i_1;
    }
    return (dp_i_0 + dp_i_1) % MAX_NUM;
}

欢迎交流，批评指正！