Fastest Solution || Full Explanation
IntuitionHere we are given with two condition.
1 : No two adjacent houses are painted the same color.
2 : Houses equidistant from the ends of the row are not pa
# Intuition
Here we are given with two condition.
1 : No two adjacent houses are painted the same color.
2 : Houses equidistant from the ends of the row are not painted the same color. eg (0, n -1) (1, n -2) and number are houses are even

for i th house we not only have to look for (i - 1) but also we need to consider (n - (i - i)) house also.
Each House has 3 color option.
So Considering all above Points we are going to calculate cost of two houses (i & (n -i)) at a time.


If we consider paints as a, b, c
So total 9 combination for painting 2 rows 
But we can't color them with same color so aa, bb, cc can be ignored
rest for all 6 we find value and find min 

Ex. 
0a 0b 0c
1a 1b 1c
2a 2b 2c
3a 3b 3c
4a 4b 4c
5a 5b 5c

0a --> 0th house with a color paint
suppose we need to find min cost for house 1 & 4
and out of 6 combination we are looking at 1b & 4a

here along with their cost we also need to look prv. possiblity and take min of those. We will be having total of 9 possibility for 0 & 5
now we will remove invalid combination out of these 9.
3 will be removed as they will be same paint combination. so we are left with only 6

house 1 is painted with color b so house 0 can not be using paint b which will remove 0b & 5a and 0b & 5c 
Similary 4th is painted with a so 5th house can't use a color which remove 5a & 0b and 5a & 0c.
in above example 5a & 0b came twice 
So in the end we are just going to compare it with 3 value




# Approach
1 : Find min for all 6 valid comb for 0 and n-1 house
2 : for all house < (n/ 2) find 6 comb along with last 3 valid min option
3 : return min of all
Here we are not using any DP matrix to avoid space 
We ca also use it to avoid reassignment But at end we need last used row

 
# Complexity
- Time complexity:
O(n)

- Space complexity:
O(1)

# Fastest Solution with clear Explanation
Pls upvote!!!!

# Code
```java []
class Solution {
    public long minCost(int n, int[][] cost) {
        long colAB = cost[0][0] + cost[n - 1][1];
        long colAC = cost[0][0] + cost[n - 1][2];
        long colBA = cost[0][1] + cost[n - 1][0];
        long colBC = cost[0][1] + cost[n - 1][2];
        long colCA = cost[0][2] + cost[n - 1][0];
        long colCB = cost[0][2] + cost[n - 1][1];
        long newColAB, newColAC, newColBA, newColBC, newColCA, newColCB;
        for (int i = 1, lim = n/2; i < lim; i++) {
            newColAB = Math.min(Math.min(colBA, colBC), colCA) + cost[i][0] + cost[n - 1 - i][1]; 
            newColAC = Math.min(Math.min(colBA, colCA), colCB) + cost[i][0] + cost[n - 1 - i][2];
            newColBA = Math.min(Math.min(colAB, colAC), colCB) + cost[i][1] + cost[n - 1 - i][0];
            newColBC = Math.min(Math.min(colAB, colCA), colCB) + cost[i][1] + cost[n - 1 - i][2];
            newColCA = Math.min(Math.min(colAB, colAC), colBC) + cost[i][2] + cost[n - 1 - i][0];
            newColCB = Math.min(Math.min(colAC, colBA), colBC) + cost[i][2] + cost[n - 1 - i][1];
            colAB = newColAB;
            colAC = newColAC;
            colBA = newColBA; 
            colBC = newColBC; 
            colCA = newColCA; 
            colCB = newColCB;
        }
        return Math.min(Math.min(colAB, colAC), Math.min(Math.min(colBA, colBC), Math.min(colCA, colCB)));
    }
}
```
['Dynamic Programming', 'Java']