---
# System prepended metadata

title: 1411. Number of Ways to Paint N × 3 Grid
tags: [Leetcode, Dynamic Programming, Hard]

---

# 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```行整体的喷涂方案总数。于是

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

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

要注意的是check function的写法
不能写成
```java
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
```java=
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;
    }
}
```