Easy C++ Solution || Beats 100 % || Runtime 19ms || Array & Dynamic Programming || 
IntuitionThis problem involves finding the minimum cost to paint a sequence of n items with specific rules about adjacent relationships. Here's the intuition be
# Intuition
This problem involves finding the minimum cost to paint a sequence of n items with specific rules about adjacent relationships. Here's the intuition behind the optimized solution:<!-- Describe your first thoughts on how to solve this problem. -->

# Observation 

1. **Pair Mirroring 🪞**:  
   The array is split into two halves, and each element in the first half is paired with its corresponding mirrored element in the second half.

2. **Six Possible Transitions 🎨**:  
   For each pair, there are six valid color transitions:
   - 1 → 2, 1 → 3, 2 → 3, 2 → 1, 3 → 1, and 3 → 2.

3. **Dynamic Programming State 📊**:  
   Use a "dp" array where each index tracks the minimum cost for one of the six transitions at every step.

4. **Transition Dependencies 🔄**:  
   The cost for a state at step "i" depends on the minimum cost of valid transitions from step "i-1", ensuring no consecutive items have the same state.

5. **Minimization of Costs 💰**:  
   At each step, compute the minimum cost for all transitions and update the "dp" values accordingly. 

6. **Efficiency ⚡**:  
   By iteratively updating the "dp" array and reusing space, the algorithm runs in \(O(n)\) time and \(O(1)\) space.

# Approach

1. **Divide the Array 🪞**:  
   Split the array into two halves, pairing each element in the first half with its mirrored element in the second half.  

2. **Initialize Base Cases 🎨**:  
   Compute the cost for all six possible transitions (1 → 2, 1 → 3, 2 → 3, etc.) for the first pair of items.  

3. **Iterative Transitions 🔄**:  
   For each subsequent pair, calculate the minimum cost for all six transitions based on the previous "dp" values. Add the current pair's painting costs.  

4. **Track Minimum Cost 💰**:  
   Use dynamic programming to keep track of the minimum cost for each transition at every step.  

5. **Return Result 🏆**:  
   After processing all pairs, return the smallest value in the "dp" array as the result.  <!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity:
O(n) :- One pass for initialization and O(n/2) iterations for updates.<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:
O(1) :- Uses two 1D arrays of size 6.<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
public:
    long long minCost(int n, vector<vector<int>>& cost) {
        int half = n / 2;
        vector<long long> dp(6, 0), temp(6, 0);
        
        dp[0] = cost[0][0] + cost[n-1][1]; 
        dp[1] = cost[0][0] + cost[n-1][2]; 
        dp[2] = cost[0][1] + cost[n-1][2]; 
        dp[3] = cost[0][1] + cost[n-1][0]; 
        dp[4] = cost[0][2] + cost[n-1][0]; 
        dp[5] = cost[0][2] + cost[n-1][1]; 

        for (int i = 1; i < half; ++i) {
            temp[0] = min({dp[2], dp[3], dp[4]}) + cost[i][0] + cost[n-i-1][1]; 
            temp[1] = min({dp[3], dp[4], dp[5]}) + cost[i][0] + cost[n-i-1][2]; 
            temp[2] = min({dp[0], dp[4], dp[5]}) + cost[i][1] + cost[n-i-1][2]; 
            temp[3] = min({dp[0], dp[1], dp[5]}) + cost[i][1] + cost[n-i-1][0]; 
            temp[4] = min({dp[0], dp[1], dp[2]}) + cost[i][2] + cost[n-i-1][0]; 
            temp[5] = min({dp[1], dp[2], dp[3]}) + cost[i][2] + cost[n-i-1][1]; 
            dp = temp; 
        }
        
        return *min_element(dp.begin(), dp.end());
    }
};

```
['Array', 'Dynamic Programming', 'Memoization', 'C++']