⭐ Simple & Efficient DP Solution ✅ | Python 🐍 | Full Explanation & Visualization 🔥
IntuitionThe problem requires us to paint n houses such that:
No two adjacent houses have the same color.
Houses equidistant from both ends must also have diffe
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The problem requires us to paint n houses such that:
1. No two adjacent houses have the same color.
1. Houses equidistant from both ends must also have different colors.

Given n ≤ 10⁵, a brute-force approach (O(3ⁿ)) would be too slow. Instead, we use Dynamic Programming (DP) to efficiently track the minimum painting cost while maintaining the constraints.

# Approach 
<!-- Describe your approach to solving the problem. -->
We use DP with rolling updates to track valid color combinations for each house pair ```(i, n-i-1)```.
Instead of storing the entire DP table, we only store the previous iteration to reduce space complexity.

## DP State Representation
- Let ```dp[(left, right)]``` represent the minimum cost to paint house ```i``` (left color) and house ```n-i-1``` (right color) while maintaining constraints.
- State Transition Formula: $$dp[i][left][right] = cost[i][left] + cost[n - i - 1][right] + \min(\text{valid previous DP states})$$
- We maintain only the last computed state (O(1) space complexity).

## Step-by-Step DP Table Updates
We pair houses symmetrically:

- House 0 is paired with House n-1
- House 1 is paired with House n-2
- House 2 is paired with House n-3, and so on...

Example
Input

```
n = 6
cost = [
    [2, 4, 6],
    [5, 3, 8],
    [7, 1, 9],
    [4, 6, 2],
    [3, 5, 7],
    [8, 2, 4]
]

```

### 🚀 Step 1: Initialize DP for First and Last House (0,5)
We start by calculating the minimum painting cost for **House 0** and **House 5**, considering all valid color combinations.

| House 0 Color | House 5 Color | Cost Calculation | DP Value |
|--------------|--------------|------------------|----------|
| Red (0)  | Green (1) | $$2 + 2 = 4$$ | $$(0,1) → 4$$ |
| Red (0)  | Blue (2)  | $$2 + 4 = 6$$ | $$(0,2) → 6$$ |
| Green (1)| Red (0)   | $$4 + 8 = 12$$ | $$(1,0) → 12$$ |
| Green (1)| Blue (2)  | $$4 + 4 = 8$$ | $$(1,2) → 8$$ |
| Blue (2) | Red (0)  | $$6 + 8 = 14$$ | $$(2,0) → 14$$ |
| Blue (2) | Green (1) | $$6 + 2 = 8$$ | $$(2,1) → 8$$ |

Updated DP Table:
```
(0,1): 4   (0,2): 6
(1,0): 12  (1,2): 8
(2,0): 14  (2,1): 8

```

## 🚀 Step 2: Process House Pair (1,4)

| House 1 Color | House 4 Color | Base Cost | Min Valid Prev DP | Updated DP Value |
|--------------|--------------|-----------|------------------|------------------|
| Red (0)  | Green (1) | $$5 + 5 = 10$$ | $$\min(8, 12, 14) = 8$$ | $$10 + 8 = 18$$ |
| Red (0)  | Blue (2)  | $$5 + 7 = 12$$ | $$\min(8, 12, 14) = 8$$ | $$12 + 8 = 20$$ |
| Green (1)| Red (0)   | $$3 + 3 = 6$$  | $$\min(4, 6, 8) = 4$$ | $$6 + 4 = 10$$ |
| Green (1)| Blue (2)  | $$3 + 7 = 10$$ | $$\min(4, 14, 8) = 4$$ | $$10 + 4 = 14$$ |
| Blue (2) | Red (0)   | $$8 + 3 = 11$$ | $$\min(4, 6, 8) = 4$$ | $$11 + 4 = 15$$ |
| Blue (2) | Green (1) | $$8 + 5 = 13$$ | $$\min(6, 12, 8) = 6$$ | $$13 + 6 = 19$$ |

Updated DP Table:
```
(0,1): 18   (0,2): 20
(1,0): 10   (1,2): 14
(2,0): 15   (2,1): 19
```

## 🚀 Step 3: Process House Pair (2,3)

| House 2 Color | House 3 Color | Base Cost | Min Valid Prev DP | Updated DP Value |
|--------------|--------------|-----------|------------------|------------------|
| Red (0)  | Green (1) | $$7 + 6 = 13$$ | $$\min(10, 14, 15) = 10$$ | $$13 + 10 = 23$$ |
| Red (0)  | Blue (2)  | $$7 + 2 = 9$$  | $$\min(10, 15, 19) = 10$$ | $$9 + 10 = 19$$ |
| Green (1)| Red (0)   | $$1 + 4 = 5$$  | $$\min(20, 18, 19) = 18$$ | $$5 + 18 = 23$$ |
| Green (1)| Blue (2)  | $$1 + 2 = 3$$  | $$\min(15, 18, 19) = 15$$ | $$3 + 15 = 18$$ |
| Blue (2) | Red (0)   | $$9 + 4 = 13$$ | $$\min(14, 18, 20) = 14$$ | $$13 + 14 = 27$$ |
| Blue (2) | Green (1) | $$9 + 6 = 15$$ | $$\min(14, 10, 20) = 10$$ | $$15 + 10 = 25$$ |

Updated DP Table:
```
(0,1): 23   (0,2): 19
(1,0): 23   (1,2): 18
(2,0): 27   (2,1): 25
```

##  Final Answer: 
```min(dp.values()) = 18```

# Complexity
- Time complexity: O(n)
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
    - We iterate over n/2 house pairs.
    - Each step considers only valid color transitions (constant work).

- Space complexity: O(1)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
    We store only the previous DP state, keeping memory minimal.

# Code
```python3 []
class Solution:
    def minCost(self, n: int, cost: List[List[int]]) -> int:
         # Initialize DP for the first and last house pairing
        dp = {
            (left, right): cost[0][left] + cost[n-1][right]
            for left in range(3) for right in range(3) if left != right
        }

        # Process houses from the outermost towards the center
        for i in range(1, n // 2):
            # Initialize new DP state for the current house pair (i, n-i-1)
            new_dp = {
                (left, right): cost[i][left] + cost[n-i-1][right]
                for left in range(3) for right in range(3) if left != right
            }

            # Update costs by finding the minimum valid previous state
            for (left, right) in new_dp:
                new_dp[(left, right)] += min(
                    dp[(prev_left, prev_right)]
                    for (prev_left, prev_right) in dp
                    if left != prev_left and right != prev_right
                )
            dp = new_dp # Update DP table for the next iteration
        return min(dp.values()) # Return the minimum cost across all valid coloring configurations
```

# Approach with an array 
This optimized approach uses a flat list (```dp``` of size 6) instead of a dictionary. The logic remains the same:

- We iterate over house pairs ```(i, n-i-1)```, computing valid coloring costs.
- Instead of using a dictionary ```dp[(left, right)]```, we store the 6 valid coloring combinations in a list.

This approach optimizes the DP transition by using a flat list of size 6 instead of a dictionary. Each index in ```dp``` represents a valid color combination for house pairs ```(i, n-i-1)```, ensuring that adjacent and equidistant houses never share the same color. At each step, the cost of painting the current house pair is added to the minimum valid cost from the previous state. Instead of maintaining a full DP table, we overwrite dp at every iteration, reducing space complexity to O(1).

The key idea is that each house pair contributes to the next DP state, where ```dp[i]``` stores the minimum cost of valid color assignments. The transition is handled efficiently by computing the lowest possible cost from previously computed values. Since there are always 6 possible valid coloring pairs, the time complexity remains O(n), and the rolling update ensures constant space usage. This method is highly optimized for large inputs ```n = 10⁵```. 🚀

# Code
```python3 []
class Solution:
    def minCost(self, n: int, cost: List[List[int]]) -> int:
        dp = [0] * 6
        for i in range(n >> 1):
            dp = [
                cost[i][0] + cost[n - i - 1][1] + min(dp[2:5]),
                cost[i][0] + cost[n - i - 1][2] + min([dp[2]] + dp[4:]),
                cost[i][1] + cost[n - i - 1][0] + min(dp[:2] + [dp[5]]),
                cost[i][1] + cost[n - i - 1][2] + min([dp[0]] + dp[4:]),
                cost[i][2] + cost[n - i - 1][0] + min(dp[:2] + [dp[3]]),
                cost[i][2] + cost[n - i - 1][1] + min(dp[1:4]),
            ]
        return min(dp)
```

# Complexity
- Time complexity: O(n)
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: O(1)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
['Array', 'Dynamic Programming', 'Python3']