🔥 🔥 🔥 Kotlin, simple DP, O(n) time, O(1) space, beats 100%
IntuitionThis is a typical dynamic programming problem. It does require a little more thought on how to encode the state of the problem.If we can somehow encode
# Intuition
This is a typical dynamic programming problem. It does require a little more thought on how to encode the state of the problem.

If we can somehow encode the minimum cost for painting the houses up to index `i - 1` for each possible color `j` of the `house[i - 1]`, we can calculate the minimum cost for painting the houses up to index `i` by adding to painting cost for house `i` to the minimum of the costs for houses up to `i - 1` such that the colors of houses `i - 1` and `i` are different.

But what about the second constraint that "equidistant" houses have to have different colors?

Well, instead of our state just describing "*the minimum cost of houses painted up to index `i` with the last house having color `1`, `2`, `3`*", our state will be "*`i` houses from either end have been painted, with the `i`th house from the left having color `1`, `2`, `3` and the `i`th house from the right having color `1`, `2`, `3`*".

This means we have to maintain an array `dp` of dimensions `3x3`.

# Approach
We declare our `3x3` array of `Long`s and initiate it with `Long.MAX_VALUE`. Since equidistant houses cannot have the same color, we leave the combinations for the first and last house having the same colors `1`, `2`, `3` at this maximum value.

We can populate the other six possible color combinations `0,1`, `0,2`, `1, 0`, `1, 2`, `2,0`, `2,1` according to the values from the `cost` array.

In our loop, we calculate our new states `n / 2 - 1` more times.

## Example
The minimum cost to paint the next two houses (the `i`th house from the left and the `i`th house from the right) the colors `1` and `2` respectively is the minimum of the costs of the houses painted so far, where the previous left house has either color `2` or `3` and the previous right house has color either `1` or `3`, and of course we can skip considering the cost where __both__ houses have color `3`, because that would violate the "equidistant" constraint.

To this minimum, we add the cost of painting house `i` from the left in color `1` and the cost of painting house `i` from the right in color `2`.


# Complexity
- Time complexity: O(`n`), since we loop `n \ 2` times

- Space complexity: O(`1`), since we only need to keep track of 9 states.

# Code
```kotlin []
class Solution {
    fun minCost(n: Int, cost: Array<IntArray>): Long {
        // dp[j][k] = min cost for all houses painted up to index `i` from the left, and up to index `n - 1 - i`
        //            from the right with the house at index `i` being painted in color `j` + 1 and the house at
        //            index `k` in color `k` + 1
        var dp = Array(3) { LongArray(3) { Long.MAX_VALUE } }
        dp[0][1] = cost[0][0].toLong() + cost[n - 1][1]
        dp[0][2] = cost[0][0].toLong() + cost[n - 1][2]
        dp[1][0] = cost[0][1].toLong() + cost[n - 1][0]
        dp[1][2] = cost[0][1].toLong() + cost[n - 1][2]
        dp[2][0] = cost[0][2].toLong() + cost[n - 1][0]
        dp[2][1] = cost[0][2].toLong() + cost[n - 1][1]

        for (i in 1 until n / 2) {
            val nextDp = Array(3) { LongArray(3) { Long.MAX_VALUE } }
            nextDp[0][1] = minOf(dp[1][0], dp[1][2], dp[2][0]) + cost[i][0] + cost[n - 1 - i][1]
            nextDp[0][2] = minOf(dp[1][0], dp[2][0], dp[2][1]) + cost[i][0] + cost[n - 1 - i][2]
            nextDp[1][0] = minOf(dp[0][1], dp[0][2], dp[2][1]) + cost[i][1] + cost[n - 1 - i][0]
            nextDp[1][2] = minOf(dp[0][1], dp[2][0], dp[2][1]) + cost[i][1] + cost[n - 1 - i][2]
            nextDp[2][0] = minOf(dp[0][1], dp[0][2], dp[1][2]) + cost[i][2] + cost[n - 1 - i][0]
            nextDp[2][1] = minOf(dp[0][2], dp[1][0], dp[1][2]) + cost[i][2] + cost[n - 1 - i][1]
            dp = nextDp
        }

        return dp.minOf { it.min() }
    }
}
```
['Dynamic Programming', 'Kotlin']