线性动态规划：打家劫舍 III（进阶版——树形DP + 状态机）

题目描述
你是一个专业的小偷，计划偷窃沿街的房屋。这些房屋的排列不是一条直线，而是一棵二叉树。每个房屋都存放着特定金额的钱。相邻的房屋如果直接相连（即父子节点关系）则不能同时被偷窃。你需要在不触动警报的情况下，一夜之内能够偷窃到的最高金额。

二叉树定义

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

示例
输入：

     3
    / \
   2   3
    \   \
     3   1

输出：7
解释：偷窃节点 3（根节点）、节点 3（右子树的右子节点）和节点 3（左子树的右子节点），金额为 3 + 3 + 1 = 7。

解题过程循序渐进讲解

步骤1：理解问题与约束

• 房屋是二叉树节点，每个节点有金额（非负整数）。
• 不能同时偷窃直接相连的节点（即偷了父节点就不能偷子节点，反之亦然）。
• 目标：选择节点集合，使得节点不相邻且总金额最大。

这实际是一个树形DP问题，但本质仍是线性DP思想在树结构上的扩展。

步骤2：定义状态
对每个节点，我们需要考虑两种状态：

• 偷这个节点：则不能偷它的直接子节点。
• 不偷这个节点：则可以偷或不偷它的子节点（取最优）。

定义 dp[node] 为一个长度为2的数组：

• dp[node][0]：表示不偷节点 node 时，以 node 为根的子树能偷到的最大金额。
• dp[node][1]：表示偷节点 node 时，以 node 为根的子树能偷到的最大金额。

步骤3：状态转移方程
从叶子节点向根节点递归计算：

1. 如果偷当前节点 node：

   • 不能偷左右子节点，所以只能取左右子节点“不偷”的状态。
   • dp[node][1] = node.val + dp[node.left][0] + dp[node.right][0]

2. 如果不偷当前节点 node：

   • 可以自由选择偷或不偷左右子节点，分别取左右子节点的两种状态的最大值。
   • dp[node][0] = max(dp[node.left][0], dp[node.left][1]) + max(dp[node.right][0], dp[node.right][1])

步骤4：初始化与递归边界

• 空节点：dp[None] = [0, 0]（不偷和偷的金额都是0）。
• 叶子节点：dp[leaf][1] = leaf.val，dp[leaf][0] = 0。
• 递归计算左右子树，再按转移方程合并。

步骤5：举例演示
用示例树：

     3
    / \
   2   3
    \   \
     3   1

节点标记为：

• A(3) 根
• B(2) 左子
• C(3) 右子
• D(3) B的右子
• E(1) C的右子

自底向上计算：

1. 节点 D(3)：
   • 不偷：dp[D][0] = 0
   • 偷：dp[D][1] = 3
2. 节点 B(2)：
   • 不偷：max(dp[D][0], dp[D][1]) = max(0, 3) = 3
   • 偷：2 + dp[D][0] = 2 + 0 = 2
     → dp[B] = [3, 2]
3. 节点 E(1)：
   • 不偷：0
   • 偷：1
     → dp[E] = [0, 1]
4. 节点 C(3)：
   • 不偷：max(dp[E][0], dp[E][1]) = max(0, 1) = 1
   • 偷：3 + dp[E][0] = 3 + 0 = 3
     → dp[C] = [1, 3]
5. 节点 A(3) 根：
   • 不偷：max(dp[B][0], dp[B][1]) + max(dp[C][0], dp[C][1]) = max(3, 2) + max(1, 3) = 3 + 3 = 6
   • 偷：3 + dp[B][0] + dp[C][0] = 3 + 3 + 1 = 7
     → dp[A] = [6, 7]

最终结果：max(dp[root][0], dp[root][1]) = max(6, 7) = 7

步骤6：算法实现（Python）

def rob(root):
    def dfs(node):
        if not node:
            return (0, 0)  # (不偷, 偷)
        left = dfs(node.left)
        right = dfs(node.right)
        # 不偷当前节点
        not_rob = max(left[0], left[1]) + max(right[0], right[1])
        # 偷当前节点
        rob_cur = node.val + left[0] + right[0]
        return (not_rob, rob_cur)
    
    res = dfs(root)
    return max(res)

时间复杂度：O(n)，n 为节点数，每个节点访问一次。
空间复杂度：O(h)，h 为树高，递归栈空间。

步骤7：思考扩展

• 如果要求输出偷的节点集合？可以在递归时记录选择，最后回溯路径。
• 如果树变成图（相邻节点更多），则问题变为一般图上的最大权独立集，是 NP-hard 问题。
• 如果允许偷相邻节点但罚款？可引入更复杂的状态（如偷相邻罚款系数）。

这个题目是“打家劫舍”系列从线性到树形的自然延伸，核心是状态机DP在树上的后序遍历应用。