[C++/Python] DP & DFS & Bitmask - Picture explain - Clean & Concise
Note\n- Simillar to problem: 1411. Number of Ways to Paint N \xD7 3 Grid, but in this case, the number of rows is not fixed to 3, it\'s a dynamic values <= 5. S
**Note**\n- Simillar to problem: [1411. Number of Ways to Paint N \xD7 3 Grid](https://leetcode.com/problems/number-of-ways-to-paint-n-3-grid/discuss/574912), but in this case, the number of rows is not fixed to 3, it\'s a dynamic values <= 5. So we need to use dfs to generate all possible columns.\n- Use DP to calcuate number of ways.\n- Since `M <= 5`, we can fill colors of matrix column by column. To store previous column state in DP, we can use BitMask, each 2 bits store a color (1=Red, 2=Green, 3=Blue, 0=White), so there is total 4^M column states.\n\n![image](https://assets.leetcode.com/users/images/a79897f2-eef0-4966-b551-b3b0b1cc84e8_1625980167.5595653.png)\n\n<iframe src="https://leetcode.com/playground/XwDXM7KE/shared" frameBorder="0" width="100%" height="730"></iframe>\n\n**Complexity**\n- Time: `O(N * 3^M * 2^M)`, where `N <= 1000` is number of columns, `M <= 5` is number of columns.\n\t- There is total: `N * 3^M` states in dp params, each state has up to `(2^M)` neighbors to calculate.\n\t- Why up to `2^M` neighbors each state? Because choose color of cell (0, c) has up to 2 ways *(different color from cell(0, c-1))*, choose color of cell (1, c) has up to ways *(different color from both cell(1, c-1) and cell(0, c))*... until `M` rows.\n- Space: \n\t- C++: `O(N * 4^M + 4^M * 2^M)`, because in C++ we use memory 4^M=1024 to store colors of states.\n\t- Python: `O(N * 3^M + 3^M * 2^M)`, because in Python @lru_cache up to 3^M colors of column states (red, green, blue).\n\n\n**Another version dfs neighbors in the dp function**\n<iframe src="https://leetcode.com/playground/NBz6CQzy/shared" frameBorder="0" width="100%" height="530"></iframe>
[]