hi maxwell
ExplanationInstead of building one array of length n, let's build two arrays A and B of length n // 2, where:
A[i−1]=A[i]
B[i−1]=B[i]
A[i]=B[i]
It's clear th
### Explanation

Instead of building one array of length `n`, let's build two arrays `A` and `B` of length `n // 2`, where:

1. $$A[i-1] \neq A[i]$$
2. $$B[i-1] \neq B[i]$$
3. $$A[i] \neq B[i]$$

It's clear that this is an identical problem to the original, just easier to think about.

Let $$\text{dp}(i, \text{prevA}, \text{prevB})$$ represent the minimum cost to fill in the rest of the arrays if:
- $$A[0 \ldots i-1]$$ and $$B[0 \ldots i-1]$$ are already filled,
- $$A[i-1] = \text{prevA}$$,
- $$B[i-1] = \text{prevB}$$.

Then, we can iterate through all pairs $$(c_1, c_2)$$ to fill in $$A[i] = c_1$$ and $$B[i] = c_2$$, where:

1. $$c_1 \neq \text{prevA}$$
2. $$c_2 \neq \text{prevB}$$
3. $$c_1 \neq c_2$$

The coloring cost to color the current index is:

$$
\text{costA}[i][c_1] + \text{costB}[i][c_2]
$$

And the cost to color the rest is:

$$
\text{dp}(i+1, c_1, c_2)
$$

As we have colored $$A[i]$$ and $$B[i]$$, we move on, where:
- $$\text{prevA}$$ is now equal to $$c_1$$,
- $$\text{prevB}$$ is now equal to $$c_2$$.

So:

$$
\text{dp}(i, \text{prevA}, \text{prevB}) =
\min \Big(
    \text{costA}[i][\text{c1}] + \text{costB}[i][\text{c2}] + \text{dp}(i+1, \text{c1}, \text{c2})
\Big)
$$

Subject to the conditions:
- $$0 \leq \text{c1}, \text{c2} < 3$$
- $$\text{c1} \neq \text{c2}$$
- $$\text{c1} \neq \text{prevA}$$
- $$\text{c2} \neq \text{prevB}$$


# Code
```python3 []
class Solution:
    def minCost(self, n: int, cost: List[List[int]]) -> int:
        # turn cost into costA and costB.
        costA = []
        costB = []

        for i in range(n):
            if i < n//2:
                costA.append(cost[i])
            else:
                costB.append(cost[i])
            
        costB = costB[::-1]

        # we are building an array of length n//2, not length n
        n //= 2

        @cache
        def dp(i, prevA, prevB):
            if i == n: # all done
                return 0

            ans = inf
            # try all candidates for A and B
            for c1 in range(3):
                for c2 in range(3):
                    # if they are equal to each other or they are equal to their previous chosen, then it is invalid
                    if c1 == prevA or c2 == prevB or c1 == c2:
                        continue
                    # cost of painting A[i] = c1 plus cost of painting B[i] = c2
                    coloringCost = costA[i][c1] + costB[i][c2]

                    # A[i] is now colored, so i = i+1
                    # previous for A is now c1
                    # previous for B is now c2
                    ans = min(ans, coloringCost + dp(i+1, c1, c2))

            return ans
        # prevA = -1 and prevB = -1 so that the first c1 and c2 are unrestricted
        return dp(0, -1, -1)
```
['Python3']