Hiểu bài toán

Bài toán yêu cầu tìm cách sơn N ngôi nhà liên tiếp nhau sao cho:

1. Hai ngôi nhà liền kề không được sơn cùng màu.
2. Tổng chi phí sơn là nhỏ nhất. Mỗi ngôi nhà i có 3 phương án sơn (Xanh, Hồng, Vàng) với chi phí tương ứng là a[i][0], a[i][1], a[i][2]. Ví dụ với N=4, ta có thể chọn dãy màu Vàng - Hồng - Xanh - Vàng với tổng chi phí là 137.

Các cách tiếp cận

Cách Quy hoạch động cơ bản

#include <bits/stdc++.h>
using namespace std;
int n;
int a[100005], b[100005], c[100005];
int dp_x[100005]; // Chi phí nhỏ nhất khi sơn nhà i màu Xanh
int dp_h[100005]; // Chi phí nhỏ nhất khi sơn nhà i màu Hồng
int dp_v[100005]; // Chi phí nhỏ nhất khi sơn nhà i màu Vàng

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i] >> c[i];
    }
    // Khởi tạo cho nhà đầu tiên
    dp_x[1] = a[1];
    dp_h[1] = b[1];
    dp_v[1] = c[1];

    // Quy hoạch động
    for(int i = 2; i <= n; i++) {
        dp_x[i] = min(dp_h[i-1] + a[i], dp_v[i-1] + a[i]);
        dp_h[i] = min(dp_x[i-1] + b[i], dp_v[i-1] + b[i]);
        dp_v[i] = min(dp_x[i-1] + c[i], dp_h[i-1] + c[i]);
    }

    cout << min(dp_x[n], min(dp_h[n], dp_v[n]));
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(N)

Approach này sử dụng 3 mảng DP để lưu chi phí nhỏ nhất khi sơn nhà thứ i với từng màu cụ thể. Với mỗi nhà i, ta tính:

• dpx[i] = chi phí sơn nhà i màu Xanh + min(dph[i-1], dp_v[i-1])
• dph[i] = chi phí sơn nhà i màu Hồng + min(dpx[i-1], dp_v[i-1])
• dpv[i] = chi phí sơn nhà i màu Vàng + min(dpx[i-1], dp_h[i-1]) Cuối cùng, kết quả là min của 3 giá trị tại nhà cuối cùng.

Cách Quy hoạch động tối ưu bộ nhớ

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct House {
   ll x, h, v; // x: Xanh, h: Hồng, v: Vàng
};
House f[100005];

int main() {
   ll n;
   cin >> n;
   for(int i = 1; i <= n; i++)
      cin >> f[i].x >> f[i].h >> f[i].v;

   // Quy hoạch động từ nhà thứ 2 trở đi
   for(int i = 2; i <= n; i++) {
      f[i].x += min(f[i-1].h, f[i-1].v);
      f[i].h += min(f[i-1].x, f[i-1].v);
      f[i].v += min(f[i-1].x, f[i-1].h);
   }

   ll result = min(f[n].x, min(f[n].h, f[n].v));
   cout << result;
}

• Time Complexity: O(N)
• Space Complexity: O(N)

Cách tiếp cận này tối ưu hơn bằng cách sử dụng struct để lưu trữ 3 giá trị DP cho mỗi nhà. Thay vì dùng 3 mảng riêng biệt, ta dùng 1 mảng cấu trúc. Logic tính toán tương tự như cách 1 nhưng code ngắn gọn và dễ quản lý hơn.

Cách Quy hoạch động với vector 2 chiều

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

vector<vector<int>> dp(1e5+1, vector<int>(3, 1e4+1));
vector<vector<int>> cost(1e5+1, vector<int>(3));

int main() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= 2; j++) {
            cin >> cost[i][j];
        }
    }

    // Khởi tạo DP[0] = 0 cho cả 3 màu
    dp[0][0] = dp[0][1] = dp[0][2] = 0;

    for(int i = 1; i <= n; i++) {
        dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + cost[i][0];
        dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + cost[i][1];
        dp[i][2] = min(dp[i-1][1], dp[i-1][0]) + cost[i][2];
    }

    cout << min({dp[n][0], dp[n][1], dp[n][2]});
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(N)

Approach này sử dụng vector 2 chiều với kích thước N x 3. DP[i][j] biểu diễn chi phí nhỏ nhất khi sơn nhà i với màu j (0=Xanh, 1=Hồng, 2=Vàng). Với mỗi nhà i, ta cập nhật DP[i][j] bằng chi phí sơn nhà i màu j cộng với chi phí nhỏ nhất của nhà i-1 với 2 màu còn lại. Cách này dễ mở rộng nếu có nhiều màu hơn.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán có tính chất optimal substructure: cách sơn tối ưu cho N nhà phụ thuộc vào cách sơn tối ưu cho N-1 nhà trước đó
• Với mỗi nhà, ta chỉ cần quan tâm đến màu sơn của ngôi nhà trước đó, không cần quan tâm đến toàn bộ dãy trước
• DP state: dp[i][color] = chi phí nhỏ nhất để sơn i nhà đầu tiên, với nhà thứ i được sơn màu 'color'

Lỗi thường gặp

• Quên khởi tạo giá trị cho nhà đầu tiên (base case), dẫn đến kết quả sai
• Sử dụng biến toàn cục nhưng không reset giữa các test case (trong trường hợp có nhiều test cases)
• Sử dụng int thay vì long long cho N lớn (10^5) và chi phí lên đến 10^4, tổng chi phí có thể lên đến 10^9, gây tràn số