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。

自建示例

一行网格共有十二种合法染色:

输入:n = 1
输出:12
解释:首格有三种选择,第二格有两种,第三格有两种,共 3 * 2 * 2 = 12。

两行还需满足竖直方向约束:

输入:n = 2
输出:54
解释:枚举第一行的两类颜色模式并转移到第二行,共得到 54 种合法方案。