493，动态规划解打家劫舍 III

Original 山大王wld 数据结构和算法 2022-05-01

收录于合集 #算法图文分析 161个

The world is a book, and those who do not travel read only a page.

世界是一本书，不旅行的人只读了其中的一页。

问题描述

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

示例 1:

输入: [3,2,3,null,3,null,1]

3 / \ 2 3 \ \ 3 1

输出: 7 解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.

示例 2:

输入: [3,4,5,1,3,null,1]

3 / \ 4 5 / \ \ 1 3 1

输出: 9解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.

动态规划解决

前面我们刚讲过484，打家劫舍 II和479，递归方式解打家劫舍，今天这题和之前讲的这两道题完全不同，因为前面两题所偷窃的房屋都是数组，而这题是一个二叉树。但这道题也可以使用动态规划来解决。

对于二叉树的每一个节点都有两种状态，一种是偷，一种是不偷。我们定义一个长度为2的数组dp，其中dp[0]表示不偷当前这个节点所能偷窃的最高金额，dp[1]表示偷当前节点所能偷窃的最高金额。

我们就从根节点开遍历这棵二叉树。

如果偷根节点，那么就不能偷根节点的两个子节点，所以

dp[1]=root.val+left.dp[0]+right.dp[0];

这里的伪代码left.dp[0]表示的是不能偷当前节点的左子节点

如果不偷根节点，那么我们可以偷子节点也可以不偷子节点，我们取最大值即可，所以

dp[0]=max(left.dp[0],left.dp[1])+max(right.dp[0],right.dp[1]);

那么边界条件是什么呢，就是节点为空的时候，直接返回0即可。

有了递推公式和边界条件，我们来看下最终代码

 1public int rob(TreeNode root) {
 2    int[] robHelp = robHelper(root);
 3    //取偷根节点和不偷根节点的最大值
 4    return Math.max(robHelp[1], robHelp[0]);
 5}
 6
 7public int[] robHelper(TreeNode root) {
 8    //边界条件
 9    if (root == null)
10        return new int[2];
11    //这里的left是个长度为2的一维数组，其中left[0]表示不偷root.left节点
12    //所能偷窃的最大金额，left[1]表示偷root.left节点所能偷窃的最大金额。
13    int[] left = robHelper(root.left);
14    //right节点同left
15    int[] right = robHelper(root.right);
16    //Math.max(right[0], right[1]), root.val + left[0] + right[0]表示
17    //的是不能偷当前节点，所以可以偷两个子节点，也可以不偷子节点，我们取最大的。
18    //root.val + left[1] + right[1]表示的是偷当前节点，所以不能偷两个子节点。
19    return new int[]{Math.max(left[0], left[1]) +
20            Math.max(right[0], right[1]), root.val + left[0] + right[0]};
21}