House Robber

Bài toán

Bạn là một tên trộm chuyên nghiệp. Mỗi ngôi nhà có một số tiền nhất định nums[i]. Hệ thống an ninh sẽ báo động nếu bạn trộm hai ngôi nhà liền kề. Hỏi số tiền lớn nhất bạn có thể trộm được là bao nhiêu?

Ví dụ:

Input: [1, 2, 3, 1]
Output: 4
Chọn 1 và 3 => Tổng = 4. (Không thể chọn 2 và 3 vì liền kề).

Phân Tích & Tiếp Cận

Tư duy QHĐ

Tại ngôi nhà thứ i (có tiền n), ta có 2 lựa chọn:

1. Cướp nhà này: Ta lấy tiền n, nhưng bắt buộc phải bỏ qua nhà i-1. Số tiền lúc này = n + maxTiền(i-2).
2. Bỏ qua nhà này: Ta giữ nguyên số tiền max kiếm được tại nhà i-1. Số tiền lúc này = maxTiền(i-1).

Hàm mục tiêu: dp[i] = max(nums[i] + dp[i-2], dp[i-1]).

Code Reference

Ta lại chỉ cần 2 biến để lưu trữ rob1 (i-2) và rob2 (i-1).

function rob(nums: number[]): number {
    let rob1 = 0;
    let rob2 = 0;

    // [rob1, rob2, n, n+1, ...]
    for (const n of nums) {
        const temp = Math.max(n + rob1, rob2);
        rob1 = rob2;
        rob2 = temp;
    }

    return rob2;
}

• Time Complexity: $O(n)$.
• Space Complexity: $O(1)$.

Pattern Nhận Diện

• Dạng bài "Chọn hay Bỏ" (Take or Skip).
• Ràng buộc không được chọn liền kề.
• Tối ưu hóa giá trị (Max/Min).