House Robber: pattern DP hai bước bỏ qua kề nhau

Bài trước kết thúc với House Robber được liệt kê là bài liên quan: "không được cướp hai nhà liền kề; dp[i] = max(nums[i] + dp[i+2], dp[i+1])". Dòng đó gánh hết phần nặng, nhưng lại bỏ qua phần thực sự mất thời gian để thấm — tại sao ràng buộc kề nhau lại thu gọn về đúng hai biến và không gì thêm.

Đề bài

Bạn là một tên trộm chuyên nghiệp lên kế hoạch cướp các ngôi nhà dọc một con phố. Mỗi nhà chứa một lượng tiền nhất định, nhưng các nhà liền kề có hệ thống bảo mật kết nối với nhau — cướp hai nhà liền kề trong cùng một đêm sẽ tự động báo cảnh sát. Cho mảng số nguyên nums trong đó nums[i] là số tiền trong nhà i, trả về số tiền tối đa có thể cướp mà không kích hoạt báo động. Xem đề đầy đủ tại: LeetCode 198.

Ràng buộc:
- 1 <= nums.length <= 100
- 0 <= nums[i] <= 400

Ràng buộc làm cho bài này thú vị

Cho một dãy nhà. Nhà i chứa nums[i] đô. Bạn có thể cướp bất kỳ tập con nào, trừ việc không được cướp hai nhà liền kề nhau. Bài toán hỏi tổng tối đa bạn có thể lấy được.

Ràng buộc đó chính là toàn bộ độ khó. Nếu không có nó, bạn cộng hết tất cả là xong. Với nó, tại mỗi nhà i bạn phải quyết định: lấy nhà này và cộng với bất cứ thứ gì tối ưu từ hai bước trở về trước, hay bỏ qua và giữ nguyên kết quả tốt nhất từ nhà ngay trước.

Constraints của bài nói lên một điều khá nhẹ nhàng: 1 <= nums.length <= 100 và 0 <= nums[i] <= 400. Một trăm nhà, mỗi nhà trị giá tối đa 400 đô. Array nhỏ đến mức O(n^2) vẫn pass được — nhưng DP recurrence chạy O(n) đằng nào. Giá trị không âm quan trọng hơn vẻ ngoài của chúng: chúng đảm bảo bạn không bao giờ có lợi khi cố tình bỏ qua một nhà mà bạn có thể cướp mà không kích hoạt báo động. Sự phân nhánh chỉ bị ép buộc bởi tính kề nhau, không phải vì giá trị âm khiến một số nhà đáng tránh. Nếu giá trị có thể âm, toàn bộ bài toán sẽ có hình dạng khác.

nums = [2, 7, 9, 3, 1] — tối ưu là 2 + 9 + 1 = 12. Cướp nhà 0, 2, và 4, bỏ qua 1 và 3.

nums = [1, 2, 3, 1] — tối ưu là 1 + 3 = 4. Bỏ qua nhà 1 (giá trị 2) để lấy nhà 2 (giá trị 3).

Từ Min Cost Climbing Stairs đến House Robber

Min Cost Climbing Stairs có dp[i] = cost[i] + min(dp[i+1], dp[i+2]). Dạng bài là lookback hai bước: từ vị trí i, nhìn một hoặc hai vị trí tiếp theo và kết hợp kết quả.

House Robber có đúng cùng dạng đó, lật chiều và dùng max thay vì min. Định nghĩa dp[i] là số tiền tối đa lấy được từ nhà 0 đến nhà i. Tại mỗi nhà:

dp[i] = max(dp[i-1], dp[i-2] + nums[i])

Nhánh trái — bỏ qua nhà i: kết quả tốt nhất qua nhà i-1. Nhánh phải — cướp nhà i: bắt buộc đã bỏ qua nhà i-1, nên kết quả tốt nhất là qua nhà i-2, cộng với nums[i].

Recurrence hoàn chỉnh. Không có trường hợp nào khác.

Approach 1: Đệ quy thuần (Brute Force) — O(2^n)

Bắt đầu từ index 0 và phân nhánh tại mỗi nhà. Lấy nó hoặc bỏ qua nó.

class Solution:
    def rob(self, nums):
        def robFrom(index):
            if index >= len(nums):
                return 0
            rob_current = nums[index] + robFrom(index + 2)
            skip_current = robFrom(index + 1)
            return max(rob_current, skip_current)
        return robFrom(0)

public class Solution {
    public int Rob(int[] nums) {
        return RobFrom(nums, 0);
    }
    private int RobFrom(int[] nums, int index) {
        if (index >= nums.Length) return 0;
        int robCurrent = nums[index] + RobFrom(nums, index + 2);
        int skipCurrent = RobFrom(nums, index + 1);
        return Math.Max(robCurrent, skipCurrent);
    }
}

Mỗi lời gọi phân nhánh thành hai, và bạn chạm đến base case ở độ sâu n. Cây đệ quy có O(2^n) nút. Độ sâu call stack là O(n). Bản này bị reject với input trên ~30 nhà — không phải vì constraints của bài đủ lớn để ép, mà vì sự bùng nổ theo hàm mũ là có thật.

Vấn đề là overlapping subproblems. Để thấy rõ, hãy trace cây đệ quy với nums = [2, 7, 9, 3, 1]:

robFrom(3) xuất hiện ba lần (nút vàng). robFrom(4) xuất hiện ba lần. Mọi subproblem dùng chung đều bị tính lại từ đầu. Brute force không có bộ nhớ về công việc đã làm.

Approach 2: Memoization (Top-Down DP) — O(n) time, O(n) space

Cache kết quả lần đầu gặp và trả về ngay trong các lần sau.

class Solution:
    def rob(self, nums):
        memo = {}
        def robFrom(index):
            if index in memo:
                return memo[index]
            if index >= len(nums):
                return 0
            rob_current = nums[index] + robFrom(index + 2)
            skip_current = robFrom(index + 1)
            memo[index] = max(rob_current, skip_current)
            return memo[index]
        return robFrom(0)

public class Solution {
    private Dictionary<int, int> memo = new Dictionary<int, int>();
    public int Rob(int[] nums) {
        memo.Clear();
        return RobFrom(nums, 0);
    }
    private int RobFrom(int[] nums, int index) {
        if (memo.ContainsKey(index)) return memo[index];
        if (index >= nums.Length) return 0;
        int robCurrent = nums[index] + RobFrom(nums, index + 2);
        int skipCurrent = RobFrom(nums, index + 1);
        memo[index] = Math.Max(robCurrent, skipCurrent);
        return memo[index];
    }
}

Mỗi index từ 0 đến n-1 chỉ được tính một lần. Dictionary thêm O(n) space; call stack thêm O(n) nữa. Bản memoization hữu ích để kiểm tra logic của recurrence vì nó phản ánh trực tiếp cách phân nhánh. Nhưng tôi sẽ không submit bản này — bản iterative đơn giản hơn để suy nghĩ về và không có recursion overhead.

Approach 3: Tabulation (Bottom-Up DP) — O(n) time, O(n) space

Đổi chiều hoàn toàn. Điền mảng dp từ trái sang phải. Base case cần chút cẩn thận cho hai nhà đầu tiên.

class Solution:
    def rob(self, nums):
        n = len(nums)
        if n == 0: return 0
        if n == 1: return nums[0]
        dp = [0] * n
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
        for i in range(2, n):
            dp[i] = max(dp[i-1], dp[i-2] + nums[i])
        return dp[n-1]

public class Solution {
    public int Rob(int[] nums) {
        int n = nums.Length;
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        int[] dp = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.Max(nums[0], nums[1]);
        for (int i = 2; i < n; i++)
            dp[i] = Math.Max(dp[i-1], dp[i-2] + nums[i]);
        return dp[n-1];
    }
}

dp[1] = max(nums[0], nums[1]) đáng dừng lại một chút. Với hai nhà, bạn chọn cái có giá trị hơn — không thể lấy cả hai. Đây là chỗ duy nhất mà quy tắc "bỏ qua kề nhau" tạo ra lựa chọn giữa hai giá trị cụ thể thay vì hai nhánh recurrence.

Trace tay đầy đủ với nums = [2, 7, 9, 3, 1]:

Đáp án: 12 — lấy nhà 0 (2) + nhà 2 (9) + nhà 4 (1).

Mỗi bước tại index i chỉ hỏi một câu: dp[i-1] (bỏ qua nhà i) có tốt hơn dp[i-2] + nums[i] (cướp nhà i) không? Không gì khác quan trọng. Nếu cần dựng lại những nhà nào bị cướp thay vì chỉ tổng tiền, mảng dp là thứ bạn trace ngược — nên O(n) space trong trường hợp đó thực sự xứng đáng.

Approach 4: Space-Optimized DP — O(n) time, O(1) space

Mảng tabulation tốn O(n), nhưng recurrence chỉ nhìn về hai vị trí trước. Mọi thứ trước dp[i-2] là rác thải. Thay mảng bằng hai biến vô hướng.

class Solution:
    def rob(self, nums):
        n = len(nums)
        if n == 0: return 0
        if n == 1: return nums[0]
        prev2 = nums[0]
        prev1 = max(nums[0], nums[1])
        for i in range(2, n):
            current = max(prev1, prev2 + nums[i])
            prev2 = prev1
            prev1 = current
        return prev1

public class Solution {
    public int Rob(int[] nums) {
        int n = nums.Length;
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        int prev2 = nums[0];
        int prev1 = Math.Max(nums[0], nums[1]);
        for (int i = 2; i < n; i++) {
            int current = Math.Max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = current;
        }
        return prev1;
    }
}

prev2 là dp[i-2]. prev1 là dp[i-1]. current là dp[i]. Sau khi tính current, trượt cửa sổ về phía trước: prev2 = prev1, prev1 = current. Thứ tự quan trọng — prev2 cần prev1 cũ trước khi prev1 bị ghi đè, nên cập nhật prev2 trước.

Đây là bản tôi để lại trong codebase.

So sánh các approach

Các edge case

nums = [1] — một nhà duy nhất. Guard n == 1 trả về nums[0] trước khi vòng lặp bắt đầu. Không có guard, prev1 = max(nums[0], nums[1]) sẽ truy cập ngoài giới hạn mảng.

nums = [1, 2] — hai nhà liền kề, trả về max(1, 2) = 2. Base case dp[1] = max(nums[0], nums[1]) (hoặc khởi tạo prev1) xử lý gọn; thân vòng lặp không bao giờ chạy vì range(2, 2) rỗng.

nums = [2, 1, 1, 2] — mảng đối xứng. Cướp nhà 0 và 3: 2 + 2 = 4. Không cần special-case; recurrence tự đến dp = [2, 2, 3, 4]. Tại index 3, dp[1] + nums[3] = 2 + 2 = 4 thắng dp[2] = 3.

nums = [0, 0, 0] — tất cả bằng 0. Recurrence cho ra tất cả 0 và trả về 0. Không cần logic edge-case; giá trị không âm đảm bảo kết quả luôn >= 0.

Constraint không âm (0 <= nums[i] <= 400) làm cho recurrence gọn. Nếu giá trị có thể âm, một nhà có thể đáng tránh ngay cả khi không có ràng buộc kề nhau, và bạn sẽ cần state phong phú hơn. Giá trị không âm thu gọn chiều đó: lý do duy nhất để bỏ qua nhà i là tính kề nhau với nhà i-1, chỉ vậy thôi.

Nhận diện dạng bài

Các keyword tố cáo recurrence này: "maximum", "cannot take adjacent elements", "optimal choice at each position". Tổng quát hơn, bất kỳ bài nào khi:

• Bạn có một dãy quyết định tuyến tính.
• Chọn phần tử i loại bỏ phần tử i-1 (hoặc một lân cận kích thước cố định).
• Bạn đang tối đa hóa hoặc tối thiểu hóa tổng trên các phần tử được chọn.

Khi thấy đủ ba dấu hiệu đó, với tay ngay vào lookback hai bước trước. Viết brute force recursion để xác nhận recurrence, memoize để kiểm tra tính đúng hiệu quả, sau đó chuyển sang bottom-up và nén về hai biến.

Bốn bài sibling dùng cùng skeleton

House Robber II (213) — các nhà tạo thành một vòng tròn, nên nhà 0 và nhà n-1 là kề nhau. Không thể dùng single-pass trực tiếp. Mẹo: chạy space-optimized rob trên nums[0..n-2] và riêng trên nums[1..n-1], rồi lấy max của cả hai. Cùng recurrence, hai lần gọi.

House Robber III (337) — các nhà được sắp xếp trong một binary tree. Kề nhau giờ có nghĩa là cha-con. Mẹo hai biến không port trực tiếp; bạn mang một cặp (rob, skip) từ mỗi subtree lên qua post-order DFS. Logic recurrence giống hệt — rob node này và lấy giá trị skip của cả hai con, hoặc skip node này và lấy max của mỗi con — nhưng cấu trúc dữ liệu thay đổi.

Delete and Earn (740) — không thể lấy một số nếu đã lấy số kém hoặc hơn nó một đơn vị. Khi nhận ra nó tương đương với một bucket array nơi lấy bucket i cấm bucket i-1 và i+1, nó rút gọn trực tiếp về House Robber. Ràng buộc kề nhau là như nhau; cách biểu diễn khác.

Decode Ways (91) — linear DP với decision-making tại mỗi vị trí. Dạng recurrence khác nhau, nhưng pattern "tại mỗi index, quyết định dựa trên cửa sổ lookback cố định" là cùng một bản năng.

Sợi chỉ kết nối tất cả: bất cứ lúc nào bạn có một dãy nơi chọn phần tử i loại bỏ một tập hàng xóm nào đó và bạn đang tối ưu một tổng, lookback hai bước đáng thử trước.