LC 3429. Paint House IV

https://leetcode.com/problems/paint-house-iv/description/

Tag: DP

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;
    }
};

本題主要的重點在左右對稱的地方不可以塗上相同的顏色，根據這個規定我們可以大概知道 DP 的方向。

本題的 DP 是要從中間開始往左右兩邊進行計算，這樣可以同時保證不會有連續相同的顏色以及對稱位置的顏色不同。