1411. Number of Ways to Paint N × 3 Grid ======================================== 题目信息 -------- :题号: 1411 :难度: Hard :主题: 动态规划、状态压缩、计数 :原题: `LeetCode 1411 `_ :重点: 使用三种颜色给 ``n x 3`` 网格染色,任何水平或竖直相邻格颜色不同;答案取模 题目重述 -------- 给定正整数 ``n``,使用红、黄、绿三种颜色给 ``n`` 行 ``3`` 列的网格染色。 要求任意共享边的两个格子颜色不同。请返回合法染色方案数量对 ``10^9 + 7`` 取模后的结果。 ``1 <= n <= 5000``。 自建示例 -------- 一行网格共有十二种合法染色: .. code-block:: text 输入:n = 1 输出:12 解释:首格有三种选择,第二格有两种,第三格有两种,共 3 * 2 * 2 = 12。 两行还需满足竖直方向约束: .. code-block:: text 输入:n = 2 输出:54 解释:枚举第一行的两类颜色模式并转移到第二行,共得到 54 种合法方案。