C++ DP Solution
CodeBlog Link
# Code
```cpp []
typedef long long ll;
class Solution {
public:
    long long minCost(int n, vector<vector<int>>& cost) {
        int mid = n / 2 + n % 2;
        vector<vector<vector<ll>>> f(mid, vector<vector<ll>>(3, vector<ll>(3, LLONG_MAX)));
        if (n % 2) {
            for (int i = 0; i < 3; i++)
                for (int j = 0; j < 3; j++) {
                    if (i == j) continue;
                    f[0][i][j] = cost[mid][i];
                }
        } else {
            for (int i = 0; i < 3; i++)
                for (int j = 0; j < 3; j++) {
                    if (i == j) continue;
                    f[0][i][j] = cost[mid - 1][i] + cost[mid][j];
                }
        }
        for (int i = 1; i < mid; i++) {
            int cur_r = mid + i;
            int cur_l = mid - i - (n % 2 == 0);
            int pre_r = cur_r - 1;
            int pre_l = cur_l + 1;
            for (int pre_l_c = 0; pre_l_c < 3; pre_l_c++) {
                for (int pre_r_c = 0; pre_r_c < 3; pre_r_c++) {
                    if (pre_l_c == pre_r_c) continue;
                    for (int cur_l_c = 0; cur_l_c < 3; cur_l_c++) {
                        if (cur_l_c == pre_l_c) continue;
                        for (int cur_r_c = 0; cur_r_c < 3; cur_r_c++) {
                            if (cur_l_c == cur_r_c || cur_r_c == pre_r_c) continue;
                            f[i][cur_l_c][cur_r_c] = min(f[i][cur_l_c][cur_r_c], f[i - 1][pre_l_c][pre_r_c] + cost[cur_l][cur_l_c] + cost[cur_r][cur_r_c]);
                        }
                    }
                }
            }
        }

        ll ans = LLONG_MAX;
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++) {
                if (i == j) continue;
                ans = min(ans, f[mid - 1][i][j]);
            }
        return ans;
    }
};
```

[Blog Link](https://www.zephyrhuang.org/lc-3429-paint-house-iv/)

['Dynamic Programming', 'C++']