Easy to understand dynamic programming solution
IntuitionThe question looks like a limited dynamic programming problem, we can easily to ensure conditon 1, but meanwhile,we must ensure the condition 2.
Condit
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The question looks like a limited dynamic programming problem, we can easily to ensure conditon 1, but meanwhile,we must ensure the condition 2.
> **Condition 1**: No two adjacent houses are painted the same color. 
**Condition 2**: Houses equidistant from the ends of the row are not painted the same color. For example, if n = 6, houses at positions (0, 5), (1, 4), and (2, 3) are considered equidistant.
# Approach
<!-- Describe your approach to solving the problem. -->
The sequential iteration from left to right can't ensure condition 2, but we observed the input array is even, and there are only 3 colors, as a result, we can iterate the dp array from central to both slides.

For the central elements, they are asked to use different colors, if we named the color to 1,2,3, then we can get 6 combinations. We define an array with size 6, then use 0 to represent the left element use color 1, the right elements use color 2. 
The full state definition:
-  0: left element use color 1, right element use color 2 (Can adjacent to state 2,3,4)
-  1: 13 (Can adjacent to state 3,4,5)
-  2: 23 (Can adjacent to state 0,4,5)
-  3: 21 (Can adjacent to state 0,1,5)
-  4: 31 (Can adjacent to state 0,1,2)
-  5: 32 (Can adjacent to state 1,2,3)
 
**State Transition Logic** 
Each state s can only transition from predecessor states that avoid color conflicts. For example:

State 12 (left=1, right=2) can transition from states where the predecessor’s right color ≠ 1 and left color ≠ 2 (e.g., 23, 31, 21).

Predefined allowed transitions between states ensure efficient computation.
# Complexity
- Time complexity:
$$O(n)$$
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:
$$O(n)$$
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
public:
    long long minCost(int n, vector<vector<int>>& cost) {
        vector<vector<long long>> dp(cost.size(), vector<long long>(6, -1));
        for(int i=0;i<n/2;i++){
            // color: 1 2 3
            // 0: 12 (2,3,4)
            // 1: 13 (3,4,5)
            // 2: 23 (0,4,5)
            // 3：21 (0,1,5)
            // 4：31 (0,1,2)
            // 5：32 (1,2,3)
            // left: n/2-i-1, right: n/2+i
            int left = n/2-i-1, right = n/2+i;
            if(i == 0){
                dp[i][0] = cost[left][0]+cost[right][1];
                dp[i][1] = cost[left][0]+cost[right][2];
                dp[i][2] = cost[left][1]+cost[right][2];
                dp[i][3] = cost[left][1]+cost[right][0];
                dp[i][4] = cost[left][2]+cost[right][0];
                dp[i][5] = cost[left][2]+cost[right][1];
                continue;
            }
            dp[i][0] = min(dp[i-1][4], min(dp[i-1][2], dp[i-1][3])) + cost[left][0]+cost[right][1];
            dp[i][1] = min(dp[i-1][4], min(dp[i-1][5], dp[i-1][3])) +  cost[left][0]+cost[right][2];
            dp[i][2] = min(dp[i-1][4], min(dp[i-1][5], dp[i-1][0])) +  cost[left][1]+cost[right][2];
            dp[i][3] = min(dp[i-1][0], min(dp[i-1][1], dp[i-1][5])) +  cost[left][1]+cost[right][0];
            dp[i][4] = min(dp[i-1][0], min(dp[i-1][1], dp[i-1][2])) +  cost[left][2]+cost[right][0];
            dp[i][5] = min(dp[i-1][1], min(dp[i-1][2], dp[i-1][3])) +  cost[left][2]+cost[right][1];
        }

        long long res = LONG_MAX;
        for(int i=0;i<6;i++){
            // cout<<dp[n/2-1][i]<<endl;
            res = min(dp[n/2-1][i], res);
        }
        return res;
    }
};
```
['C++']