1411. Number of Ways to Paint N × 3 Grid

ref:

[Java] Detailed Explanation with Graph Demo - DP - Easy Understand - undefined - LeetCodeLeetCode

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

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)

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;
    }
}