Tìm giá trị trộm cắp tối đa từ dãy nhà trong C++

Mô tả vấn đề

Cho n ngôi nhà với giá trị tiền trong mảng houses[]. Tên trộm không thể cướp 2 nhà liền kề (hàng xóm sẽ biết). Tìm giá trị lớn nhất có thể cướp được.

Ví dụ minh họa

Đầu vào:

houses[] = {5, 2, 1, 6, 7, 9, 4, 3}

Đầu ra:

23

Giải thích:

Cướp các nhà: 5, 6, 9, 3 → Tổng = 23

Phương pháp giải quyết

Quy hoạch động (DP):

• DP[i] = giá trị max cướp được từ nhà 0 đến i
• Cơ sở: DP[0] = houses[0], DP[1] = max(houses[0], houses[1])
• Chuyển trạng thái: DP[i] = max(houses[i] + DP[i-2], DP[i-1]) (Cướp nhà i + max đến i-2, HOẶC không cướp nhà i → max đến i-1)
• Kết quả: DP[n-1]

Tối ưu không gian O(1): Chỉ cần 2 biến val1 (DP[i-2]) và val2 (DP[i-1]).

Chương trình minh họa (DP mảng)

#include <iostream>
using namespace std;

int calMax(int a, int b) { return (a > b) ? a : b; }

int findMaxValuesStolen(int houses[], int n) {
    if (n == 0) return 0;
    int DP[n];
    DP[0] = houses[0];
    DP[1] = calMax(houses[0], houses[1]);
    for (int i = 2; i < n; i++)
        DP[i] = calMax(houses[i] + DP[i-2], DP[i-1]);
    return DP[n-1];
}

int main() {
    int houses[] = {5, 2, 1, 6, 7, 9, 4, 3};
    int n = sizeof(houses) / sizeof(houses[0]);
    cout << "Giá trị trộm cắp tối đa là " << findMaxValuesStolen(houses, n);
    return 0;
}

Chương trình minh họa (Tối ưu O(1) space)

int findMaxValuesStolen(int houses[], int n) {
    if (n == 0) return 0;
    int val1 = houses[0];
    int val2 = calMax(houses[0], houses[1]);
    int maxValStolen;
    for (int i = 2; i < n; i++) {
        maxValStolen = calMax(houses[i] + val1, val2);
        val1 = val2;
        val2 = maxValStolen;
    }
    return maxValStolen;
}

Kết quả đầu ra

Giá trị trộm cắp tối đa là 23