💥💥 Beats 100% on runtime and memory [EXPLAINED]
Intuition\nColoring a grid such that no two adjacent cells have the same color, leveraging the limited number of colors (red, green, blue) to create valid combi
# Intuition\nColoring a grid such that no two adjacent cells have the same color, leveraging the limited number of colors (red, green, blue) to create valid combinations while ensuring that all cells are painted.\n\n# Approach\nGenerate all valid color combinations for a single row, build an adjacency list representing valid transitions between these combinations, and use a depth-first search (DFS) with memoization to count the number of ways to paint the grid based on the constraints.\n\n# Complexity\n- Time complexity:\nO(n\u22C53 m ), where \uD835\uDC5B n is the number of rows and \uD835\uDC5A m is the number of columns, primarily due to generating valid color combinations and the DFS traversal.\n\n- Space complexity:\nO(3m + n\u22C5k), where \uD835\uDC58 k is the number of valid combinations for a row, accounting for storing the combinations and the memoization table used in DFS.\n\n# Code\n```csharp []\npublic class Solution\n{\n    private const int Mod = 1_000_000_007;\n\n    private int Dfs(int n, List<List<int>> adj, int src, int[,] dp)\n    {\n        if (n == 0) return 1;\n        if (dp[n, src] != -1) return dp[n, src];\n\n        int totalWays = 0;\n        foreach (var neighbor in adj[src])\n        {\n            totalWays = (totalWays + Dfs(n - 1, adj, neighbor, dp)) % Mod;\n        }\n\n        return dp[n, src] = totalWays;\n    }\n\n    private void GenerateValidColors(List<string> colors, int lastColor, int remaining, string current)\n    {\n        if (remaining == 0)\n        {\n            colors.Add(current);\n            return;\n        }\n\n        for (int i = 0; i < 3; i++)\n        {\n            if (lastColor != i)\n            {\n                GenerateValidColors(colors, i, remaining - 1, current + i);\n            }\n        }\n    }\n\n    private bool AreColorsCompatible(string color1, string color2)\n    {\n        for (int i = 0; i < color1.Length; i++)\n        {\n            if (color1[i] == color2[i]) return false;\n        }\n        return true;\n    }\n\n    public int ColorTheGrid(int m, int n)\n    {\n        var colorCombinations = new List<string>();\n        for (int i = 0; i < 3; i++)\n        {\n            GenerateValidColors(colorCombinations, i, m - 1, i.ToString());\n        }\n\n        var adj = new List<List<int>>(colorCombinations.Count);\n        for (int i = 0; i < colorCombinations.Count; i++)\n        {\n            adj.Add(new List<int>());\n        }\n\n        for (int i = 0; i < adj.Count; i++)\n        {\n            for (int j = 0; j < adj.Count; j++)\n            {\n                if (AreColorsCompatible(colorCombinations[i], colorCombinations[j]))\n                {\n                    adj[i].Add(j);\n                }\n            }\n        }\n\n        var dp = new int[n + 1, adj.Count];\n        for (int i = 0; i <= n; i++)\n        {\n            for (int j = 0; j < adj.Count; j++)\n            {\n                dp[i, j] = -1;\n            }\n        }\n\n        int totalWays = 0;\n        for (int i = 0; i < colorCombinations.Count; i++)\n        {\n            totalWays = (totalWays + Dfs(n - 1, adj, i, dp)) % Mod;\n        }\n\n        return totalWays;\n    }\n}\n\n```
['Dynamic Programming', 'Backtracking', 'Depth-First Search', 'C#']