C# Beats 100% in speed and memory usage
\n\n\n# Complexity\n- Time complexity:\nO(n * (3^m)^2)\n\n- Space complexity:\nO(n * 3^m + (3^m)^2)\n\n# Code\n\npublic class Solution {\n    public int ColorTh
![image.png](https://assets.leetcode.com/users/images/36b511f7-83df-4e6e-8417-6cc67b17b11e_1697676819.7317235.png)\n\n\n# Complexity\n- Time complexity:\n$$O(n * (3^m)^2)$$\n\n- Space complexity:\n$$O(n * 3^m + (3^m)^2)$$\n\n# Code\n```\npublic class Solution {\n    public int ColorTheGrid(int m, int n) {\n        var motif = new char[m];\n        var motifs = new List<string>();\n\n        motif[0] = \'R\';\n        FindMotifs(1, motif, motifs);\n\n        motif[0] = \'G\';\n        FindMotifs(1, motif, motifs);\n\n        motif[0] = \'B\';\n        FindMotifs(1, motif, motifs);\n\n        var stackables = FindStackables(motifs);\n        var dp = new int[n, motifs.Count];\n\n        for (var i = 0; i < motifs.Count; ++i) {\n            dp[0, i] = 1;\n        }\n\n        for (var i = 1; i < n; ++i) {\n            for (var j = 0; j < motifs.Count; ++j) {\n                foreach (var stackable in stackables[j]) {\n                    dp[i, j] += dp[i - 1, stackable];\n                    dp[i, j] %= 1000000007;\n                }\n            }\n        }\n\n        var ans = 0;\n\n        for (var i = 0; i < motifs.Count; ++i) {\n            ans += dp[n - 1, i];\n            ans %= 1000000007;\n        }\n\n        return ans;\n    }\n\n    private void FindMotifs(int i, char[] motif, List<string> motifs) {\n        if (i == motif.Length) {\n            motifs.Add(new string(motif));\n            return;\n        }\n\n        switch (motif[i - 1]) {\n        case \'R\':\n            motif[i] = \'G\';\n            FindMotifs(i + 1, motif, motifs);\n            motif[i] = \'B\';\n            FindMotifs(i + 1, motif, motifs);\n            break;\n        case \'G\':\n            motif[i] = \'R\';\n            FindMotifs(i + 1, motif, motifs);\n            motif[i] = \'B\';\n            FindMotifs(i + 1, motif, motifs);\n            break;\n        case \'B\':\n            motif[i] = \'R\';\n            FindMotifs(i + 1, motif, motifs);\n            motif[i] = \'G\';\n            FindMotifs(i + 1, motif, motifs);\n            break;\n        default:\n            throw new Exception();\n        }\n    }\n\n    private bool CanStack(string motifA, string motifB) {\n        for (var i = 0; i < motifA.Length; ++i) {\n            if (motifA[i] == motifB[i]) {\n                return false;\n            }\n        }\n\n        return true;\n    }\n\n    private List<int>[] FindStackables(List<string> motifs) {\n        var ans = new List<int>[motifs.Count];\n\n        for (var i = 0; i < motifs.Count; ++i) {\n            ans[i] = new();\n            \n            for (var j = 0; j < motifs.Count; ++j) {\n                if (CanStack(motifs[i], motifs[j])) {\n                    ans[i].Add(j);\n                }\n            }\n        }\n\n        return ans;\n    }\n}\n```
['C#']