[Java] Minimum cost of painting houses using K colors

We have N houses in a row and K available colors. Given a NxK matrix where each cell represents the cost of painting house N with color K, find the minimum cost of painting all the houses such that no two adjacent houses have same color.

We notice the solution can be reached using DFS recursive approach where we explore the costs of painting each house using all colors except for the one used for the previous house.

Starting from the first house we have all K choices available, however the second house will have K-1 choices since we used a color already for the first, and so on.

This means we have a O(K^N) runtime as for each house we must explore all those color choices. Our space usage will be O(N) as for each house we explore all others and that would be the depth of our stack.

We can improve on this by caching results as we go such that when we encounter the same (house, excluded color) combination again, we already have our best answer and can return that without further calculation.

We can create another NxK matrix or use a Map where the pair(house, excluded color) is the key and the value is the minimum cost of painting the current house EXCLUDING that color + cost of painting the next excluding the BEST color chosen for the current house.

By doing this, we reduce our runtime to O(NK) as for each house we explore all K colors and use O(NK) space as well for our cache.

You can check my implementation of minCostToPaintHouses on my Gist along with some tests in MinCostToPaintHousesJTests.