# 1411. Number of Ways to Paint N × 3 Grid
###### tags: `Leetcode` `Hard` `Dynamic Programming`
Link: https://leetcode.com/problems/number-of-ways-to-paint-n-3-grid/
## 思路
[1349. Maximum Students Taking Exam](https://hackmd.io/pIRFwFXgQGWTbTNDPwrYDg)的简化版
第```i```行的喷涂方法只受第```i-1```行喷涂方法的约束。所以是第I类基本型的DP问题。

考虑到每一行的喷涂方法就只有3^3=27种，是可以枚举过来的。我们可以利用状态压缩的思想，用一个小于27的整数来代表一种喷涂方法。

我们定义```dp[i][p]```表示当第```i```行喷涂```p```方案时，前```i```行整体的喷涂方案总数。于是

其中```q```就是第```i-1```行的喷涂方案，要求```q```与```p```不冲突，且```q```和```p```都是合法的。

最终的答案是最后一行所有合法喷涂方案```p```对应的dp值的总和。

要注意的是check function的写法
不能写成

int prev = -1;
while(mask!=0){
int curr = mask%3;
if(prev==curr) return false;
prev = curr;
mask /= 3;
}
return true;

这样如果是mask是0 会直接return true 但是mask0代表三个都一样颜色
## Code

class Solution {
public int numOfWays(int n) {
long[] dp = new long[27];
int mod = 1000000007;
for(int i=0; i<27; i++){
if(selfCheck(i)) dp[i] = 1;
}
for(int i=1; i<n; i++){
long[] temp = dp.clone();
for(int j=0; j<27; j++){
if(!selfCheck(j)) continue;
dp[j] = 0;
for(int k=0; k<27; k++){
if(checkDiffRow(j,k)){
dp[j] = (temp[k]+dp[j])%mod;
}
}
}
}
long ans = 0;
for(int i=0; i<27; i++){
ans = (ans+dp[i])%mod;
}
return (int)ans;
}
private boolean selfCheck(int mask){
int prev = -1;
for(int i=0; i<3; i++){
int curr = mask%3;
if(prev==curr) return false;
prev = curr;
mask /= 3;
}
return true;
}
private boolean checkDiffRow(int m1, int m2){
for(int i=0; i<3; i++){
if(m1%3==m2%3) return false;
m1/=3;
m2/=3;
}
return true;
}
}