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

淡淡的烟草味﹌ 2022-11-14 10:28 93阅读 0赞

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

给你网格图的行数 n 。

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

思路：将红黄绿分别用0，1，2来表示，我们可以得到当n=1时，一共会有12中情况出现，
    其中只有两种颜色的情况有六种：010,020,101,121,202,212;
    包括三种颜色情况的也有六种：012,021,102,120,201,210；
    
    那么当上升到二阶的时候，我们可以将其想象为两个一阶的网络进行合并，只需要符合
    相邻颜色不同而已，而能够影响到当前层的取色的，只有上一层的取色，一共有下面几种情况：
    
     - 当i-1层为010此类型，那么第i层若只有两种颜色，只能是101,202两种情况；
     - 当i-1层为010此类型，那么第i层若有三种颜色，只能是102,201两种情况；
     - 当i-1层为012此类型，那么第i层若只有两种颜色，只能是101,121两种情况；
     - 当i-1层为012此类型，那么第i层若有三种颜色，只能是120,201,210三种情况；
    
    综上所述：
    第一层情况两种颜色（fi0）的6种，三种颜色（fi1）的6种；
    第二层情况则应该是fi0=2*fi0+2*fi1，fi1=2*fi0+3*fi1；
    第n层按照此公式类推即可。

示例 1：
    
    输入：n = 1
    输出：12
    解释：总共有 12 种可行的方法：
    
    示例 2：
    
    输入：n = 2
    输出：54
    示例 3：
    
    输入：n = 3
    输出：246
    示例 4：
    
    输入：n = 7
    输出：106494
    示例 5：
    
    输入：n = 5000
    输出：30228214
     
    
    提示：
    
    n == grid.length
    grid[i].length == 3
    1 <= n <= 5000
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/number-of-ways-to-paint-n-3-grid
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。