337. House Robber III

Problem

Bài toán yêu cầu tính số tiền tối đa mà kẻ trộm có thể lấy từ các ngôi nhà được biểu diễn dưới dạng cây nhị phân. Điều kiện là không được trộm hai ngôi nhà kề nhau (liên kết trực tiếp). Đây là một bài toán điển hình sử dụng quy hoạch động kết hợp với duyệt cây (DFS).

Approach

Với mỗi node (ngôi nhà), ta có hai lựa chọn

Trộm nhà hiện tại:

Nếu chọn trộm nhà này, ta không thể trộm các nhà con trực tiếp của nó

Không trộm nhà hiện tại

Ta có thể chọn giá trị tốt nhất từ việc trộm hoặc không trộm các nhà con

Sử dụng DFS để duyệt cây và tính toán giá trị tối ưu cho node dựa trên hai lựa chọn trên

Công thức

Nếu trộm nhà hiện tại: rob_root = root.val + not_rob_left + not_rob_right

Nếu không trộm nhà hiện tại: not_rob_root = max(rob_left, not_rob_left) + max(rob_right, not_rob_right)

Time and space complexity

TC: O(n) vì mỗi node được duyệt đúng 1 lần

SC: O(h), với h là chiều cao của cây, do sử dụng stack trong quá trình đệ quy

Solution

typescripttypescript

1/**
2 * Definition for a binary tree node.
3 * class TreeNode {
4 *     val: number
5 *     left: TreeNode | null
6 *     right: TreeNode | null
7 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
8 *         this.val = (val===undefined ? 0 : val)
9 *         this.left = (left===undefined ? null : left)
10 *         this.right = (right===undefined ? null : right)
11 *     }
12 * }
13 */
14
15function rob(root: TreeNode | null): number {
16    function dfs(node: TreeNode | null): [number, number] {
17        if (!node) return [0, 0]
18        const [rob_left, not_rob_left] = dfs(node.left)
19        const [rob_right, not_rob_right] = dfs(node.right);
20
21        const rob_current = node.val + not_rob_left + not_rob_right;
22        const not_rob_current = Math.max(rob_left, not_rob_left) + Math.max(rob_right, not_rob_right);
23        return [rob_current, not_rob_current]
24    }
25
26    const [rob_root, not_rob_root] = dfs(root);
27    return Math.max(rob_root, not_rob_root)
28};

Loading content...

1/** 2 * Definition for a binary tree node. 3 * class TreeNode { 4 * val: number 5 * left: TreeNode | null 6 * right: TreeNode | null 7 * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) { 8 * this.val = (val===undefined ? 0 : val) 9 * this.left = (left===undefined ? null : left) 10 * this.right = (right===undefined ? null : right) 11 * } 12 * } 13 */ 14 15function rob(root: TreeNode | null): number { 16 function dfs(node: TreeNode | null): [number, number] { 17 if (!node) return [0, 0] 18 const [rob_left, not_rob_left] = dfs(node.left) 19 const [rob_right, not_rob_right] = dfs(node.right); 20 21 const rob_current = node.val + not_rob_left + not_rob_right; 22 const not_rob_current = Math.max(rob_left, not_rob_left) + Math.max(rob_right, not_rob_right); 23 return [rob_current, not_rob_current] 24 } 25 26 const [rob_root, not_rob_root] = dfs(root); 27 return Math.max(rob_root, not_rob_root) 28};