线性动态规划：打家劫舍 III

字数 2281 2025-11-02 00:38:37

线性动态规划：打家劫舍 III

题目描述：
你是一个专业的小偷，计划偷窃沿街的房屋。这些房屋的排列形式不是线性的，而是一棵二叉树。每个房屋都存放着特定金额的钱。唯一限制你偷窃的因素是相邻的房屋装有相互连通的防盗系统。如果两个直接相连的房屋在同一晚被闯入，系统会自动报警。给定一个二叉树的根节点 root，表示房屋的布局和每个房屋的金额，请计算在不触动警报的情况下，你今晚能够偷窃到的最高金额。

解题过程：
这个问题是“打家劫舍”系列问题的二叉树版本。关键在于，对于树中的任何一个节点，我们有两种选择：偷或者不偷。但这个选择会影响其子节点的选择。

问题分析
与线性的房屋排列不同，树形结构意味着每个节点最多有两个直接相邻的子节点（孩子），以及一个父节点。相邻的约束在这里意味着：如果你偷了一个节点，那么你就不能偷它的父节点和它的直接子节点。如果你不偷这个节点，那么它的子节点可以选择偷或者不偷。
状态定义
对于树形结构，我们通常使用深度优先搜索（DFS）来遍历。对于树中的每一个节点，我们定义一个状态数组 dp，这个数组包含两个值：
- dp[0]：表示不偷当前节点时，以当前节点为根的子树上能够偷窃到的最高金额。
- dp[1]：表示偷当前节点时，以当前节点为根的子树上能够偷窃到的最高金额。
这个状态定义是关键，它将一个复杂的全局问题分解成了每个节点的局部子问题。
状态转移方程
现在我们来看如何计算一个节点的 dp[0] 和 dp[1]。假设当前节点为 node，其左子节点为 left，右子节点为 right。
- 情况一：不偷当前节点 node
  如果决定不偷 node，那么对它的子节点 left 和 right 就没有限制了。我们可以偷 left，也可以不偷 left，取决于哪种情况能获得更多的钱。对于 right 也是同理。为了最大化总金额，我们应该为每个子节点选择其“偷”与“不偷”两种状态中的最大值。
  所以，状态转移方程为：
  dp_node[0] = max(dp_left[0], dp_left[1]) + max(dp_right[0], dp_right[1])
- 情况二：偷当前节点 node
  如果决定偷 node，那么根据相邻房屋不能同时被偷的规则，我们就绝对不能偷它的直接子节点 left 和 right。我们只能选择不偷它的子节点。
  所以，状态转移方程为：
  dp_node[1] = node.val + dp_left[0] + dp_right[0]
注意，如果 left 或 right 为空（即 node 没有某个子节点），那么对应的 dp_left 或 dp_right 的值就是 [0, 0]（因为从空节点能偷到的钱是0）。
计算顺序（递归遍历）
由于我们需要子节点（left 和 right）的状态来计算父节点（node）的状态，所以我们应该采用后序遍历（左子树 -> 右子树 -> 根节点）的方式遍历这棵树。这样，当我们处理一个节点时，它的左右子树都已经被处理完毕，我们可以直接使用它们计算好的 dp 值。
最终结果
当我们通过后序遍历处理完整个二叉树的根节点时，根节点也会有一个状态数组 dp_root。这个数组包含两个值：
- dp_root[0]：不偷根节点时整个树的最大金额。
- dp_root[1]：偷根节点时整个树的最大金额。
  整个问题的最终答案就是这两个值中的最大值：max(dp_root[0], dp_root[1])。
举例说明
考虑一个简单的二叉树：[3, 2, 3, null, 3, null, 1]
```
     3
    / \
   2   3
    \   \
     3   1
```
我们进行后序遍历（深度优先）：
- 节点 2：它的左子节点为空 (dp=[0,0])，右子节点是 3 (val=3)。
  - 计算 3 的 dp：它的左右子节点都为空。dp_3[0] = 0, dp_3[1] = 3。
  - 回到节点 2：
    - 不偷 2：max(0,0) + max(0,3) = 0 + 3 = 3
    - 偷 2：2 + 0 + 0 = 2 (不能偷子节点)
    - 所以节点 2 的 dp 是 [3, 2]。
- 节点 1（根节点的右子节点的右子节点）：左右子节点为空。dp_1[0]=0, dp_1[1]=1。
- 节点 3（根节点的右子节点）：左子节点为空，右子节点是 1。
  - 不偷这个 3：max(0,0) + max(0,1) = 0 + 1 = 1
  - 偷这个 3：3 + 0 + 0 = 3 (不能偷子节点)
  - 所以这个 3 的 dp 是 [1, 3]。
- 根节点 3：左子节点是 2 (dp=[3,2])，右子节点是 3 (dp=[1,3])。
  - 不偷根节点 3：max(3, 2) + max(1, 3) = 3 + 3 = 6
    - (从左边子树能拿到的最大金额是3，从右边子树能拿到的最大金额是3)
  - 偷根节点 3：3 + 3 + 1 = 7
    - (根节点值3 + 不偷左子节点的金额3 + 不偷右子节点的金额1)
- 最终结果：max(6, 7) = 7。
  验证：偷根节点(3)、偷左子节点的右子节点(3)、偷右子节点的右子节点(1)，总金额为 3+3+1=7，且没有触发警报（相邻的 3-2, 3-3, 2-3, 3-1 都没有同时被偷）。

线性动态规划：打家劫舍 III 题目描述：你是一个专业的小偷，计划偷窃沿街的房屋。这些房屋的排列形式不是线性的，而是一棵二叉树。每个房屋都存放着特定金额的钱。唯一限制你偷窃的因素是相邻的房屋装有相互连通的防盗系统。如果两个直接相连的房屋在同一晚被闯入，系统会自动报警。给定一个二叉树的根节点 root ，表示房屋的布局和每个房屋的金额，请计算在不触动警报的情况下，你今晚能够偷窃到的最高金额。解题过程：这个问题是“打家劫舍”系列问题的二叉树版本。关键在于，对于树中的任何一个节点，我们有两种选择：偷或者不偷。但这个选择会影响其子节点的选择。问题分析与线性的房屋排列不同，树形结构意味着每个节点最多有两个直接相邻的子节点（孩子），以及一个父节点。相邻的约束在这里意味着：如果你偷了一个节点，那么你就不能偷它的父节点和它的直接子节点。如果你不偷这个节点，那么它的子节点可以选择偷或者不偷。状态定义对于树形结构，我们通常使用深度优先搜索（DFS）来遍历。对于树中的每一个节点，我们定义一个状态数组 dp ，这个数组包含两个值： dp[0] ：表示不偷当前节点时，以当前节点为根的子树上能够偷窃到的最高金额。 dp[1] ：表示偷当前节点时，以当前节点为根的子树上能够偷窃到的最高金额。这个状态定义是关键，它将一个复杂的全局问题分解成了每个节点的局部子问题。状态转移方程现在我们来看如何计算一个节点的 dp[0] 和 dp[1] 。假设当前节点为 node ，其左子节点为 left ，右子节点为 right 。情况一：不偷当前节点 node 如果决定不偷 node ，那么对它的子节点 left 和 right 就没有限制了。我们可以偷 left ，也可以不偷 left ，取决于哪种情况能获得更多的钱。对于 right 也是同理。为了最大化总金额，我们应该为每个子节点选择其“偷”与“不偷”两种状态中的最大值。所以，状态转移方程为： dp_node[0] = max(dp_left[0], dp_left[1]) + max(dp_right[0], dp_right[1]) 情况二：偷当前节点 node 如果决定偷 node ，那么根据相邻房屋不能同时被偷的规则，我们就绝对不能偷它的直接子节点 left 和 right 。我们只能选择不偷它的子节点。所以，状态转移方程为： dp_node[1] = node.val + dp_left[0] + dp_right[0] 注意，如果 left 或 right 为空（即 node 没有某个子节点），那么对应的 dp_left 或 dp_right 的值就是 [0, 0] （因为从空节点能偷到的钱是0）。计算顺序（递归遍历）由于我们需要子节点（ left 和 right ）的状态来计算父节点（ node ）的状态，所以我们应该采用后序遍历（左子树 -> 右子树 -> 根节点）的方式遍历这棵树。这样，当我们处理一个节点时，它的左右子树都已经被处理完毕，我们可以直接使用它们计算好的 dp 值。最终结果当我们通过后序遍历处理完整个二叉树的根节点时，根节点也会有一个状态数组 dp_root 。这个数组包含两个值： dp_root[0] ：不偷根节点时整个树的最大金额。 dp_root[1] ：偷根节点时整个树的最大金额。整个问题的最终答案就是这两个值中的最大值： max(dp_root[0], dp_root[1]) 。举例说明考虑一个简单的二叉树： [3, 2, 3, null, 3, null, 1] 我们进行后序遍历（深度优先）：节点 2 ：它的左子节点为空 ( dp=[0,0] )，右子节点是 3 ( val=3 )。计算 3 的 dp：它的左右子节点都为空。 dp_3[0] = 0 , dp_3[1] = 3 。回到节点 2 ：不偷 2 ： max(0,0) + max(0,3) = 0 + 3 = 3 偷 2 ： 2 + 0 + 0 = 2 (不能偷子节点) 所以节点 2 的 dp 是 [3, 2] 。节点 1 （根节点的右子节点的右子节点）：左右子节点为空。 dp_1[0]=0 , dp_1[1]=1 。节点 3 （根节点的右子节点）：左子节点为空，右子节点是 1 。不偷这个 3 ： max(0,0) + max(0,1) = 0 + 1 = 1 偷这个 3 ： 3 + 0 + 0 = 3 (不能偷子节点) 所以这个 3 的 dp 是 [1, 3] 。根节点 3 ：左子节点是 2 (dp= [3,2] )，右子节点是 3 (dp= [1,3] )。不偷根节点 3 ： max(3, 2) + max(1, 3) = 3 + 3 = 6 (从左边子树能拿到的最大金额是3，从右边子树能拿到的最大金额是3) 偷根节点 3 ： 3 + 3 + 1 = 7 (根节点值3 + 不偷左子节点的金额3 + 不偷右子节点的金额1) 最终结果： max(6, 7) = 7 。验证：偷根节点(3)、偷左子节点的右子节点(3)、偷右子节点的右子节点(1)，总金额为 3+3+1=7，且没有触发警报（相邻的 3-2, 3-3, 2-3, 3-1 都没有同时被偷）。