Dynamic Programming with State Compression O(n)
IntuitionWe can transform the problem into a 2-row matrix (fold it). For each cell, any of the neighbour cells(sharing a wall) must not have a color that is sam
# Intuition
We can transform the problem into a 2-row matrix (fold it). For each cell, any of the neighbour cells(sharing a wall) must not have a color that is same as it.
# Approach
1. Define 6 variables, x01, x02, x10, x12, x20, x21.
2. x01 represents for the current vertical column, the cell of the first row is colored 0, and the cell of the second row is colored 1. Other variables are in the same way.
3. So   x01 = cost[0][0] + cost[lenMinus1][1], 
        x02 = cost[0][0] + cost[lenMinus1][2],
        x10 = cost[0][1] + cost[lenMinus1][0], 
        x12 = cost[0][1] + cost[lenMinus1][2],
        x20 = cost[0][2] + cost[lenMinus1][0],
        x21 = cost[0][2] + cost[lenMinus1][1]
4. Similarly, define 6 variables, y01, y02, y10, y12, y20, y21. They represent the next column's state.
5. So
        const y01 = cost[size][0] + cost[lenMinus1 - size][1] +
            Math.min(x10, x12, x20)
        const y02 = cost[size][0] + cost[lenMinus1 - size][2] +
            Math.min(x10, x20, x21)
        const y10 = cost[size][1] + cost[lenMinus1 - size][0] +
            Math.min(x01, x02, x21)
        const y12 = cost[size][1] + cost[lenMinus1 - size][2] +
            Math.min(x01, x20, x21)
        const y20 = cost[size][2] + cost[lenMinus1 - size][0] +
            Math.min(x01, x02, x12)
        const y21 = cost[size][2] + cost[lenMinus1 - size][1] +
            Math.min(x02, x10, x12)
6. Then let [x01, x02, x10, x12, x20, x21] = [y01, y02, y10, y12, y20, y21] to transit the state to the next column.
7. In this manner, go to the mid (that is, n / 2) point.
8. Math.min(x01, x02, x10, x12, x20, x21) is the result.
# Complexity
- Time complexity:
O(n)
- Space complexity:
O(1)
# Code
```javascript []
/**
 * @param {number} n
 * @param {number[][]} cost
 * @return {number}
 */
var minCost = function(n, cost) {
    const lenMinus1 = n - 1
    n >>= 1
    let x01 = cost[0][0] + cost[lenMinus1][1], 
        x02 = cost[0][0] + cost[lenMinus1][2],
        x10 = cost[0][1] + cost[lenMinus1][0], 
        x12 = cost[0][1] + cost[lenMinus1][2],
        x20 = cost[0][2] + cost[lenMinus1][0],
        x21 = cost[0][2] + cost[lenMinus1][1]


    for (let size = 1; size < n; size++) {
        const y01 = cost[size][0] + cost[lenMinus1 - size][1] +
            Math.min(x10, x12, x20)
        const y02 = cost[size][0] + cost[lenMinus1 - size][2] +
            Math.min(x10, x20, x21)
        const y10 = cost[size][1] + cost[lenMinus1 - size][0] +
            Math.min(x01, x02, x21)
        const y12 = cost[size][1] + cost[lenMinus1 - size][2] +
            Math.min(x01, x20, x21)
        const y20 = cost[size][2] + cost[lenMinus1 - size][0] +
            Math.min(x01, x02, x12)
        const y21 = cost[size][2] + cost[lenMinus1 - size][1] +
            Math.min(x02, x10, x12)

        ;[x01, x02, x10, x12, x20, x21] = [y01, y02, y10, y12, y20, y21];
    }


    const result = Math.min(x01, x02, x10, x12, x20, x21)
    return result
};
```
['JavaScript']