[Python3] DP 5 Cases
DP 5 Cases\n\nInuition\n\nThere are only 5 cases to handle (1 <= m <= 5). Since m is small the recurrence relations per m can be discovered and returned.\n\nWit
**DP 5 Cases**\n\n**Inuition**\n\nThere are only 5 cases to handle (`1 <= m <= 5`). Since `m` is small the recurrence relations per `m` can be discovered and returned.\n\nWith `m` fixed, for each time we increase `n` think in terms of possible `1*m` blocks that can be added to all existing `(n - 1)*m` blocks. \n\n**Case #1: `m == 1`**\n\nEverytime we increment `n` another block is added per existing `n - 1` block. Each 3 color block can only add 2 new blocks (different color blocks) each increment.\n\nResulting relation:\n```\na1 = 3\nan = 2*a(n-1)\n```\n\n**Case #2: `m == 2`**\n\nFrom the second example in the problem we can see that there are initially 6 `1*2` blocks. Each `1*2` block can be appended to 3 other `1*2` blocks (without causing adjacency).\n\n\nResulting relation:\n```\na1 = 6\nan = 3*a(n-1)\n```\n\n**Case #3: `m == 3`**\n\nFrom the problem example ([#1](https://leetcode.com/problems/number-of-ways-to-paint-n-3-grid/description/)) in [1411. Number of Ways to Paint N \xD7 3 Grid](https://leetcode.com/problems/number-of-ways-to-paint-n-3-grid/solutions/2957266/python3-recurrence-relation-to-dp-process/) (same problem but `m==3`) we can see that there are initially 12 `1*3` blocks. There are 2 possible patterns of `1*3` blocks complying with the adjacency restriction (divided into columns - seen below). Pattern `a` consists of 3 different colors. Pattern `b` consists of a single middle color and 2 matching end colors. When incrementing `n` each `1*3` block from the first group `a` can append 3 of its own kind and 2 from the second group `b` (without causing adjacency). When incrementing `n` each `1*3` block from the second group can append 2 of its own kind and 2 from the first group (without causing adjacency). One can brute force find the recurrence relation by taking an arbitrary block in the initial group `a` and visually examine how many blocks in the initial group `b` appended would not cause adjacency issues. One would do the same but for group `a` to itself (getting the `a` relation). One would then repeat the process with group `b` (getting the `b` relation).\n\n![3.png](https://assets.leetcode.com/users/images/60087f14-d316-41eb-bd77-19c4eb51b984_1670192178.682216.png)\n\nResulting relation:\n```\na1 = 6; b1 = 6\nan = 3*a(n-1) + 2*b(n-1)\nbn = 2*a(n-1) + 2*b(n-1)\n```\n\n**Case #4: `m == 4`**\n\nThe same methodology for `m == 3` can be performed for `m == 4` with the following groups after calculating the coefficients. Count from the following image:\n\n![4.png](https://assets.leetcode.com/users/images/2695f9a9-e2c3-4dd5-aa28-f14c4ecf97e0_1670191508.0438693.png)\n\nResulting relation:\n```\na1 = 6; b1 = 6; c1 = 6; d1 = 6\nan = 3*a(n-1) + b(n-1) + 2*c(n-1) + 2*d(n-1)\nbn = a(n-1) + 2*b(n-1) + c(n-1) + d(n-1)\ncn = 2*a(n-1) + b(n-1) + 2*c(n-1) + 2*d(n-1)\ndn = 2*a(n-1) + b(n-1) + 2*c(n-1) + 2*d(n-1)\n```\n\n**Case #5: `m == 5`**\n\nThe same methodology for `m == 4` can be performed for `m == 5` with the following groups:\n\n![5.png](https://assets.leetcode.com/users/images/90259f72-ce2b-48ab-8f43-7bfbda1ad72c_1670191524.0780618.png)\n\nResulting relation:\n```\na1 = 6; b1 = 6; c1 = 6; d1 = 6; e1 = 6; f1 = 6; g1 = 6; h1 = 6 \nan = 2*a(n-1) + b(n-1) + c(n-1) + d(n-1) + 2*e(n-1) + 2*f(n-1) + g(n-1) + h(n-1)\nbn = a(n-1) + 2*b(n-1) + c(n-1) + d(n-1) + g(n-1)\ncn = a(n-1) + b(n-1) + 2*c(n-1) + d(n-1) + e(n-1) + f(n-1) + g(n-1) + h(n-1)\ndn = a(n-1) + b(n-1) + c(n-1) + 2*d(n-1) + 2*e(n-1) + 2*f(n-1) + g(n-1) + h(n-1)\nen = 2*a(n-1) + c(n-1) + 2*d(n-1) + 3*e(n-1) + 2*f(n-1) + g(n-1) + 2*h(n-1)\nfn = 2*a(n-1) + c(n-1) + 2*d(n-1) + 2*e(n-1) + 2*f(n-1) + g(n-1) + 2*h(n-1)\ngn = a(n-1) + b(n-1) + c(n-1) + d(n-1) + e(n-1) + f(n-1) + 2*g(n-1) + h(n-1)\nhn = a(n-1) + c(n-1) + d(n-1) + 2*e(n-1) + 2*f(n-1) + g(n-1) + 2*h(n-1)\n```\n\n**Code**\n```Python3 []\nclass Solution:\n    def colorTheGrid(self, m: int, n: int) -> int:\n        \'\'\'\n            Solves a given recurrence relation\n            @params dp: the nth sum per ith equation\n            @params coeff: coefficients for the ith equation\n        \'\'\'\n        def solve_rel(dp, coeff):\n            for _ in range(n - 1):\n                for i in range(len(dp)):\n                    tmp = 0\n                    for j, c in enumerate(coeff[i]):\n                        # If j >= i we must add the second last\n                        #value appended, we already updated that dp.\n                        tmp += c*dp[j][-1 if j >= i else -2]\n                    dp[i].append(tmp)\n\n            return sum(e[-1] for e in dp) % 1000000007\n\n\n        if m == 1:\n            return solve_rel([[3]], [[2]])\n        if m == 2:\n            return solve_rel([[6]], [[3]])\n        elif m == 3:\n            return solve_rel([[6], [6]], [[3,2], [2,2]])\n        elif m == 4:\n            return solve_rel(\n                [[6], [6], [6], [6]], \n                [[3,1,2,2], [1,2,1,1], [2,1,2,2], [2,1,2,2]])\n        else:\n            return solve_rel(\n                [[6], [6], [6], [6], [6], [6], [6], [6]],\n                [\n                    [2,1,1,1,2,2,1,1], \n                    [1,2,1,1,0,0,1,0], \n                    [1,1,2,1,1,1,1,1], \n                    [1,1,1,2,2,2,1,1], \n                    [2,0,1,2,3,2,1,2], \n                    [2,0,1,2,2,2,1,2], \n                    [1,1,1,1,1,1,2,1], \n                    [1,0,1,1,2,2,1,2]\n                ])\n```
['Dynamic Programming', 'Python', 'Python3']