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