# 1411. Number of Ways to Paint N × 3 Grid

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MfBEN6rDc5eRxez6Db3%2F-MfBEQXzGsAmxbnXyBY7%2Fimage.png?alt=media\&token=1e07f581-fe08-4aff-bac6-9dd7233c4ea1)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MfBEN6rDc5eRxez6Db3%2F-MfBETe3XDTKpfvth7nc%2Fimage.png?alt=media\&token=137841c3-1eed-4c36-9188-0ddf8cf25404)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MfBEN6rDc5eRxez6Db3%2F-MfBEYYXNeA6xKh4gpRR%2Fimage.png?alt=media\&token=1ce6d658-f3de-4fbe-bc65-97c45e35e428)

#### ref:

{% embed url="<https://leetcode.com/problems/number-of-ways-to-paint-n-3-grid/discuss/574943/Java-Detailed-Explanation-with-Graph-Demo-DP-Easy-Understand>" %}

```
1. think what part I stuck?
the DP formula, 
所以要針對所有排列組合, 3*3*3 = 27, 去思考
ABC
ABA
這兩種狀況下, 排除限制條件後, 會剩幾個？

the detail of problem (vertical side, 不能一樣
也就是這一列如果是 010
下一列三個位置不能跟上一列一樣

2. see solution, think about how this person came out this solution? what’s their thought process, why we have the same question and same knowledge, but I cant?
主要還是思考排列組合的過程, 要分析 ABC ABA 兩種case

3. note strategy! remember it!
所以策略是什麼？ 要在看 leetcode 1349
```

## dp

time: O(n)

space: O(n)

notice use **long** first

```java
class Solution {
    public int numOfWays(int n) {
        // 0 ABC 012 => ABC 102, 201, ABA 101, 121
        // 1 ABA 010 => ABC 102 201, ABA 101, 121, 202
        
        // dp[i][0] = dp[i-1][0]*2 + dp[i-1][1]*2;
        // dp[i][1] = dp[i-1][0]*2 + dp[i-1][1]*3;
        
        int mod = 1000000007;
        long dp[][] = new long[n][2];
        
        dp[0][0] = 6;
        dp[0][1] = 6;
        
        for (int i = 1; i < n; i++) {
            dp[i][0] = (dp[i-1][0]*2 + dp[i-1][1]*2)%mod;
            dp[i][1] = (dp[i-1][0]*2 + dp[i-1][1]*3)%mod;
        }
        
        return (int)(dp[n-1][0] + dp[n-1][1])%mod;
    }
}
```

## use variables

time: O(n)

space: O(1)

```java
class Solution {
    public int numOfWays(int n) {
        // 0 ABC 012 => ABC 102, 201, ABA 101, 121
        // 1 ABA 010 => ABC 102 201, ABA 101, 121, 202
        
        // dp[i][0] = dp[i-1][0]*2 + dp[i-1][1]*2;
        // dp[i][1] = dp[i-1][0]*2 + dp[i-1][1]*3;
        
        int mod = 1000000007;
        
        long dp0 = 6;
        long dp1 = 6;
        
        for (int i = 1; i < n; i++) {
            long newDp0 = (dp0*2 + dp1*2)%mod;
            long newDp1 = (dp0*2 + dp1*3)%mod;
            dp0 = newDp0;
            dp1 = newDp1;
        }
        
        return (int)(dp0 + dp1)%mod;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/dynamic-programming/1411.-number-of-ways-to-paint-n-3-grid.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.