Recursion + Memoization | Java | Simple Solution
IntuitionTry all possible ways by making sure the constraints.Think of starting it from middle as we have constraint that equidistant house should not be of sam
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Try all possible ways by making sure the constraints.

Think of starting it from middle as we have constraint that equidistant house should not be of same color.
for ex: 1,2,3,4
here in first iteration, we will consider, 2 and 3. And in second iteration, we will consider 1 and 4. when we will move to further iteration, we will will pass the color we have chosen in the current iteration to next iteration, so that in next iteration we can avoid those colors.

# Approach
<!-- Describe your approach to solving the problem. -->

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

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

# Code
```java []
class Solution {

    HashMap<String,Long> map = new HashMap();
    public long minCost(int n, int[][] cost) {
        
        return minCost(n, cost, (n/2) -1, n/2, -1,-1, 0);
    }

    private long minCost(int n, int[][] cost, int left, int right, int excludeFirst, int excludeSecond, long totalCost){

        String key = (left-1) + "_" + (right+1) + "_" + (excludeSecond) + "_" + excludeFirst;

        if(map.containsKey(key)) return map.get(key);

        
        long minFinalCost = Long.MAX_VALUE;
        if(left<0 || right >= n){
            // min = Math.min(min, totalCost);
            return 0;
        }
        int first = 0;
        int second = 0;
        for(; first < cost[0].length; first++){
            if(first == excludeFirst) continue;
           int cost1 = cost[left][first];
           int cost2 = 0;
           second = 0;
           for(; second < cost[0].length; second++){
            if(second == first || second == excludeSecond) continue;
            cost2 = cost[right][second];

           long cost3 = minCost(n, cost, left-1, right+1, first, second, totalCost + cost1+cost2);
           
           minFinalCost = Math.min(cost1+cost2+cost3, minFinalCost);
           }
        }

        map.put(key, minFinalCost);
        return minFinalCost;
    }
}
```
['Java']