代码随想录笔记_动态规划_337打家劫舍III

代码随想录二刷笔记记录

LC337.打家劫舍III

---

题目

单序列问题

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

示例 1:

输入: root = [3,2,3,null,3,null,1]
输出: 7
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

示例 2:

输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9

---

思路分析

思路：

本题涉及到树，首先需要考虑遍历方式，需要前中后序遍历，或者层序遍历。实践发现，层序遍历无法成功。以单支树为反例。

因此，转而思考，左右孩子相加的值 > 父节点 ? 如果大于，则我们选择左右孩子相加的值，否则选择父节点。因此可以推导，本题需要根据递归返回的值（即左右孩子相加的值），进行判断。从而可以确定是后序遍历

动态规划五部曲 + 递归三部曲

1.确定递归函数的参数和返回值

public int[] robTree(TreeNode cur);
/*
状态1：偷当前节点所获得的最大金额。偷当前节点相当于放弃了左右孩子
状态2：不偷当前节点所获得的最大金额。不偷当前节点相当于偷左右孩子的最大值
*/

1
2
3
4
5
6

1.1 dp数组及其下标的含义

dp[0] 下标 0 记录不偷当前节点的金额总值
dp[1] 下标 1 记录偷当前节点的金额总值

1
2
3

因为本题只有2个状态，dp数组作为一个长度为2的数组

2.确定终止条件

if(null == cur) return int[0,0];
1

由终止条件可看出，dp数组初始化为 0

3.确定遍历顺序

后序遍历,通过递归函数的返回值，决定下一步dp的状态

• 递归左节点，得到 max(偷左节点的总金额，不偷左节点的总金额)
• 递归右节点，得到 max(偷右节点的总金额，不偷右节点的总金额)

int[] left = robTree(root.left);
int[] right = robTree(root.right);
1
2

4.确定单层递归逻辑

dp定义：dp[0]不偷当前节点的总金额，dp[1] 偷当前节点的总金额，则有:

int[] dp = new int[2];
//case1 : 偷当前节点，左右孩子不偷
dp[1] = cur.val + left[0] + right[0];
//case2:不偷当前节点，偷左右孩子最多金额的状态
dp[0] = Math.max(left[0],left[1]) + Math.max(riht[0],right[1]);
return dp;
1
2
3
4
5
6

5.推演分析

 //括号内为 (dp[0],dp[1])
              3   (6,7)
           /      \
   (3,2)  2        3 (1,3) 
           \        \
            3(0,3)   1 (0,1)
 dp[0] = max(left[0],left[1])=3 + max(right[0],right[1])=3 =6
 dp[1] = cur.val(3) + left[0]=3 + right[0]=1 = 7
1
2
3
4
5
6
7
8

---

代码实现

完整代码实现

public int rob(TreeNode root) {
        int[] dp = travelRob(root);
        return Math.max(dp[0],dp[1]);
    }
    public int[] travelRob(TreeNode root){
        int[] res = new int[2];
        //递归终止条件
        if (root == null){
            return res;
        }
        //单层递归逻辑
        //左
        int[] left = travelRob(root.left);
        //右
        int[] right = travelRob(root.right);
        //处理逻辑
        //1.不拿当前节点
        res[0] = Math.max(left[0],left[1]) + Math.max(right[0],right[1]);
        //2.拿当前节点
        res[1] = root.val + left[0] + right[0];
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

---

代码实现2

本题也可以采用递归的方式处理,根据后序遍历进行递归代码如下：

public int postRob(TreeNode root){
        //递归终止条件
        if (null == root){
            return 0;
        }
        //后序遍历
        int money = root.val;
        //左
        if (root.left != null){
            money += postRob(root.left.left) + postRob(root.left.right);
        }
        //右
        if (root.right != null){
            money += postRob(root.right.left) + postRob(root.right.left);
        }
        //根，返回本层偷盗的最大值
        return Math.max(money, postRob(root.left) + postRob(root.right));
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

上述代码会超时，因此优化为记忆化递归，则有

public int rob(TreeNode root) {
        Map<TreeNode,Integer> map = new HashMap<>();
        return postRobMemo(root,map);
    }
    
    public int postRobMemo(TreeNode root,Map <TreeNode,Integer> memory){
        if (root == null){
            return 0;
        }
        //递归中遇到此节点，则可以直接返回
        if (memory.containsKey(root)) {
            return memory.get(root);
        }
        int money = root.val;
        if (root.left != null) {
            money += postRobMemo(root.left.left,memory) + postRobMemo(root.left.right,memory);
        }
        if (root.right != null){
            money += postRobMemo(root.right.left,memory) + postRobMemo(root.right.right,memory);
        }
        //本层的偷盗最大值
        int res = Math.max(money,postRobMemo(root.left,memory) + postRobMemo(root.right,memory));
        memory.put(root,res);
        return res;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

---

小结

本题考察在树形结构上进行状态转移

• 首先根据题意，考虑遍历顺序。后序遍历，递归左右子树，找到两个子树返回的最大值。
• 之后，考虑递归以及状态的方式。因为本题只有偷和不偷两个状态。从这里入手，进行dp状态定义以及递归。
• 需要注意的是，子树中相邻的树层不能偷，根据这一规则，进行单层递归逻辑的处理。