✅ Easiest DP - O(1) Space - O(n) Time
dp[i][cl][cr] means ...
You are standing at the ith house and n - i - 1th house.
You have painted the i - 1th house with color cl.
You have painted the n - i -
`dp[i][cl][cr]` means ...
You are standing at the `i`th house and `n - i - 1`th house.
You have painted the `i - 1`th house with color `cl`.
You have painted the `n - i - 1`th house with color `cr`.

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

# Code
```cpp []
#define ll long long
#define v vector
#define v1 v<ll>
#define v2 v<v1>
#define v3 v<v2>
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define ROF(i, a, b) for (ll i = (a); i >= (b); i--)

class Solution {
public:
    ll minCost(int n, v<v<int>>& cost) {
        v3 dp(2, v2(4, v1(4)));
        ROF(i, n / 2 - 1, 0) {
            ROF(cl, 3, 0)
                ROF(cr, 3, 0) {
                    ll ans = 1e18;
                    FOR(j, 0, 3)
                        FOR(k, 0, 3)
                            if (j != k && j != cl && k != cr)
                                ans = min(ans, cost[i][j] + cost[n - i - 1][k] + dp[1][j][k]);
                    dp[0][cl][cr] = ans;
                }
            dp[1] = dp[0];
        }
        return dp[0][3][3];
    }
};
```

# Complexity
- Time complexity: O(n)
- Space complexity: O(n)


```cpp []
#define ll long long int
#define v vector
#define v1 v<ll>
#define v2 v<v1>
#define v3 v<v2>

class Solution {
public:
    int n; v<v<int>> cost; v3 dp;

    ll DP(int i, int cl, int cr) {
        if (i >= n / 2) return 0;
        if (dp[i][cl][cr] != -1) return dp[i][cl][cr];
        ll mini = 1e18;
        for (int j = 0; j < 3; j++)
            for (int k = 0; k < 3; k++)
                if (j != k && j != cl && k != cr)
                    mini = min(mini, cost[i][j] + cost[n - i - 1][k] + DP(i + 1, j, k));
        return dp[i][cl][cr] = mini;
    }
    ll minCost(int _n, v<v<int>>& _cost) {
        n = _n; cost = _cost; dp = v3(n + 1, v2(4, v1(4, -1)));
        return DP(0, 3, 3);
    }
};
```
['Array', 'Dynamic Programming', 'C++']