หาค่าที่ขโมยได้สูงสุดจากบ้านใน C++ (House Robber Problem)

คำอธิบายปัญหา

มี n หลังบ้าน แต่ละหลังมีค่าของมีค่า houses[i] ขโมยไม่ได้ขโมยบ้านที่ติดกัน (เพราะเพื่อนบ้านจะรู้) ต้องการหา ค่ารวมสูงสุดที่ขโมยได้

ตัวอย่าง

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

Output: 23

คำอธิบาย: ขโมยบ้าน index 0, 3, 5, 7 → ค่า = 5 + 6 + 9 + 3 = 23

แนวทางแก้ปัญหา: Dynamic Programming

กำหนด DP[i] = ค่าสูงสุดที่ขโมยได้จากบ้าน 0 ถึง i

• DP[0] = houses[0]
• DP[1] = max(houses[0], houses[1])
• DP[i] = max(DP[i-1], houses[i] + DP[i-2]) สำหรับ i ≥ 2

เหตุผล: ที่บ้าน i สามารถเลือกได้ 2 ทาง: (1) ไม่ขโมย → ค่า = DP[i-1], (2) ขโมย → ต้องไม่ขโมย i-1 → ค่า = houses[i] + DP[i-2]

โค้ดตัวอย่าง C++ (DP Array)

#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 << "The maximum possible values stolen from the houses is " << findMaxValuesStolen(houses, n);
    return 0;
}

การเพิ่มประสิทธิภาพ Space: O(1)

สังเกตว่า DP[i] ใช้แค่ DP[i-1] และ DP[i-2] → ใช้ตัวแปร 2 ตัวแทนอาร์เรย์ทั้งหมด

โค้ด C++ (Space Optimized)

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

int main() {
    int houses[] = {5, 2, 1, 6, 7, 9, 4, 3};
    int n = sizeof(houses) / sizeof(houses[0]);
    cout << "The maximum possible values stolen from the houses is " << findMaxValuesStolen(houses, n);
    return 0;
}

ผลลัพธ์

The maximum possible values stolen from the houses is 23