Number of Ways to Paint N × 3 Grid LeetCode solution in Java

1
class Solution {
2
  int MOD = 1000000007;
3
  int[][] states = {
4
    {0, 1, 0}, {1, 0, 1}, {2, 0, 1},
5
    {0, 1, 2}, {1, 0, 2}, {2, 0, 2},
6
    {0, 2, 0}, {1, 2, 0}, {2, 1, 0},
7
    {0, 2, 1}, {1, 2, 1}, {2, 1, 2}
8
  };
9

10
  HashMap<Integer, List<Integer>> nextMap = new HashMap<>();
11
  Long[][] memo;
12

13
  public int numOfWays(int n) {
14
    if (n == 0) return 0;
15

16
    // Graph
17
    for (int prev = 0; prev < 12; prev++) {
18
      List<Integer> nexts = new ArrayList<>();
19
      for (int next = 0; next < 12; next++) {
20
        if (next == prev) continue;
21

22
        boolean flag = true;
23
        for (int i = 0; i < 3; i++) {
24
          if (states[prev][i] == states[next][i]) {
25
            flag = false;
26
            break;
27
          }
28
        }
29
        if (flag) nexts.add(next);
30
      }
31
      nextMap.put(prev, nexts);
32
    }
33

34
    // DFS
35
    memo = new Long[12][n];
36
    long ways = 0;
37
    for (int i = 0; i < 12; i++) {
38
      ways += dfs(i, n - 1);
39
      ways %= MOD;
40
    }
41

42
    return (int) (ways);
43
  }
44

45
  long dfs(int prev, int n) {
46
    if (n == 0) return 1;
47

48
    if (memo[prev][n] != null) return memo[prev][n];
49

50
    long ways = 0;
51

52
    List<Integer> nexts = nextMap.get(prev);
53
    for (int next : nexts) {
54
      ways += dfs(next, n - 1);
55
      ways %= MOD;
56
    }
57

58
    memo[prev][n] = ways;
59
    return ways;
60
  }
61
}