Tô nhà II trong C++

Có n nhà xếp hàng, mỗi nhà tô 1 trong k màu. Chi phí tô nhà i màu j cho trước bằng ma trận n x k. Không được tô 2 nhà liền kề cùng màu. Tìm chi phí nhỏ nhất.

Ví dụ:

Kết quả = 5: Nhà 0 màu 0, nhà 1 màu 2 (1+4=5) hoặc nhà 0 màu 2, nhà 1 màu 0 (3+2=5).

Phương pháp giải

Quy hoạch động tối ưu O(nk). Với mỗi hàng i, tính lmins[j] = min chi phí hàng i-1 từ cột 0 đến j, rmins[j] = min từ j đến cuối. Chi phí nhà i màu j = cost[i][j] + min(lmins[j-1], rmins[j+1]).

Ví dụ chương trình

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int minCostII(vector>& costs) {
        int n = costs.size();
        int m = n ? costs[0].size() : 0;
        int ret = INT_MAX;
        
        for (int i = 1; i < n; i++) {
            vector lmins(m), rmins(m);
            lmins[0] = costs[i-1][0];
            rmins[m-1] = costs[i-1][m-1];
            for (int j = 1; j < m; j++) lmins[j] = min(costs[i-1][j], lmins[j-1]);
            for (int j = m-2; j >= 0; j--) rmins[j] = min(costs[i-1][j], rmins[j+1]);
            for (int j = 0; j < m; j++) {
                int left = (j-1 >= 0) ? lmins[j-1] : INT_MAX;
                int right = (j+1 < m) ? rmins[j+1] : INT_MAX;
                costs[i][j] += min(left, right);
            }
        }
        for (int i = 0; i < m; i++) ret = min(ret, costs[n-1][i]);
        return ret == INT_MAX ? 0 : ret;
    }
};

int main() {
    Solution ob;
    vector> v = {{1,5,3}, {2,9,4}};
    cout << ob.minCostII(v);
    return 0;
}

Đầu vào

{{1,5,3},{2,9,4}}

Đầu ra

5