https://leetcode.com/problems/painting-a-grid-with-three-different-colors/ from Google

Thinking process:

This is a grid problem, and the goal is to find the total ways to color the grid with no two adjacent cells having the same color. Usually when we talk about the total number of ways of something, especially the grid problem, we think about dynamic programming.

When applying the dynamic programming into this kind grid problem, we usually have two directions: grid by grid or row by row. “Grid by grid” means that we traverse the grid from (0,0), and then (0,1), … an so on. “Row by row” is just like what the name implies.

This problem is the “row by row” one! However, if we look into the constraints, we can see that one row can have at most 1000 elements, but one column can only have 5 elements, so instead of “row by row”, we’ll go with “column by column”. You’ll see what I mean in the next paragraph.

For each grid, we have three choices. When we go column by column, we basically want to model the state of the column into a number, which can then convert into a 5 digit string. So let’s say we have 5 elements in a column, the column will be a 5 digit sting. Each digit can be 0, 1, and 2. For example, if 0 means red, 1 means green, and 2 means blue. Then 02120 means a column of red, blue, green, blue, and red.

The convert function here is to convert a number into the 5 digit string we mentioned above. The m is the total digit we need.

 1string convert(int n, int m) {
 2    string s = "";
 3    int cnt = 0;
 4    while (cnt < m) {
 5        s += to_string(n%3);
 6        n /= 3;
 7        cnt++;
 8    }
 9    return s;
10}

If there are 5 elements in a column, it means that we have at most 3^5 choices to build a column. However, not all choices are valid because no two adjacent cells can have the same color, so we can filter out those invalid number first. We first call generateValidNum to generate a map of valid string so that we don’t waste our time to check invalid number later.

 1bool valid(string c) {
 2    int C = c.size();
 3    for (int i=1; i<C; i++) {
 4        if (c[i] == c[i-1]) return false;
 5    }
 6    return true;
 7}
 8unordered_map<string, int> generateValidNum(int m) {
 9    int limit = pow(3, m);
10    unordered_map<string, int> ret;
11    for (int i=0; i<limit; i++) {
12        string c = convert(i, m);
13        if (valid(c)) {
14            ret[c] = i;
15        }
16    }
17    return ret;
18}

After we have the valid numbers, we basically just try to go from col_1, and then col_2, … and so on. When we go from col_i to col_i+1, we just check all the combination. Let’s say col_i = 02102 and col_i+1 = 10201, we just need to check if there’s any position in these two strings is having the same number. In this example, col_i[3] = col_i+1[3] = 0, so we can’t transit from col_i to col_i+1 in this situation.

Why do we want to filter invalid numbers first? This is because if we don’t filter, then all combination of a column is at most 3^5 = 243. Then for column transition, we need to check 243^2 = 59049. To check 1000 columns, the time complexity is too big. On the contrast, if we only check the valid number, we’ll only have 3*(2^4) = 48. For the column transition, we have 48^2 = 2304. Then the total time is 2.3*10^6 which is still acceptable.

Finally, with this, we just need to go through the grid column by column, and then if the two adjacent columns are invalid, we’ll just skip the counting. Otherwise, dp[current col] += dp[previous col].

Below is the code.

 1class Solution {
 2public:
 3    bool valid(string c) {
 4        int C = c.size();
 5        for (int i=1; i<C; i++) {
 6            if (c[i] == c[i-1]) return false;
 7        }
 8        return true;
 9    }
10    string convert(int n, int m) {
11        string s = "";
12        int cnt = 0;
13        while (cnt < m) {
14            s += to_string(n%3);
15            n /= 3;
16            cnt++;
17        }
18        return s;
19    }
20    unordered_map<string, int> generateValidNum(int m) {
21        int limit = pow(3, m);
22        unordered_map<string, int> ret;
23        for (int i=0; i<limit; i++) {
24            string c = convert(i, m);
25            if (valid(c)) {
26                ret[c] = i;
27            }
28        }
29        return ret;
30    }
31    int colorTheGrid(int m, int n) {
32        int MOD = 1e9 + 7;
33        unordered_map<string, int> validNum = generateValidNum(m);
34        int limit = pow(3, m);
35        vector<int> dp1(limit);
36        for (auto& e : validNum) {
37            dp1[e.second]++;
38        }
39        for (int i=1; i<n; i++) {
40            vector<int> dp2(limit);
41            for (auto& e1 : validNum) {
42                for (auto& e2 : validNum) {
43                    bool skip = false;
44                    for (int j=0; j<m; j++) {
45                        if (e1.first[j] == e2.first[j]) skip = true;
46                    }
47                    if (not skip)
48                        dp2[e1.second] = ((long)dp2[e1.second] + dp1[e2.second]) % MOD;
49                }
50            }
51            swap(dp1, dp2);
52        }
53        int ans = 0;
54        for (int i=0; i<limit; i++) ans = ((long)ans + dp1[i]) % MOD;
55        return ans;
56    }
57};