给 N x 3 网格图涂色的方案数Java
文章发布较早，内容可能过时，阅读注意甄别。
# 题目
你有一个 n x 3 的网格图 grid ，你需要用 红，黄，绿 三种颜色之一给每一个格子上色，且确保相邻格子颜色不同（也就是有相同水平边或者垂直边的格子颜色不同）。
给你网格图的行数 n 。
请你返回给 grid 涂色的方案数。由于答案可能会非常大，请你返回答案对 10^9 + 7 取余的结果。
示例 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
# 思路
如果前一个是两色，那么这一个有3个两色和2个三色选
如果前一个是三色，那么这一个有2个两色和2个三色选
# 解法
class Solution {
public int numOfWays(int n) {
long dp2 = 6, dp3 = 6, MAX = (int)(1e9 + 7);
for (int i = 1; i < n; i++) {
long tmp2 = (dp2 * 3) % MAX + (dp3 * 2) % MAX;
long tmp3 = (dp2 * 2) % MAX + (dp3 * 2) % MAX;
dp2 = tmp2 % MAX;
dp3 = tmp3 % MAX;
}
return (int)((dp2 + dp3) % MAX);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
# 总结
- 分析出几种情况，然后分别对各个情况实现
