Question
Given non-negative values associated with houses, select a subset with maximum total value subject to adjacency constraints. ```python def rob(nums: list) -> int: ... def rob_circular(nums: list) -> int: ... def rob_tree(root) -> int: ... def rob_with_gap(nums: list, gap: int) -> int: ... ``` ## Implementation requirements 1. **Linear street:** adjacent houses cannot both be selected. For example, `rob([1,2,3,1]) == 4`. 2. **Circular street:** the first and last houses are adjacent. A single house may be selected. 3. **Tree neighborhood:** each node is a dictionary with a non-negative integer `val` and optional `left` and `right` child dictionaries (absent or `None` means no child). Selecting a node forbids its children. The input is a finite acyclic binary tree, not a shared-node graph. 4. **Configurable gap:** after selecting index `i`, another selected index must be at least `gap + 1` positions away. `gap=1` matches the linear problem. Return an integer maximum, or `0` for an empty list or `None` root, without modifying any input. Values are non-negative integers and `gap` is a non-negative integer; `gap=0` permits selecting all houses. Malformed input is outside the assessed contract. The provided `run_case` dispatches to these four interfaces. State how negative values would affect your recurrence if they were allowed. ## Design discussion (not graded) 1. Return the chosen house indices or nodes. 2. Support updates to house values between queries. 3. Generalize to an arbitrary conflict graph and discuss why the problem changes.