#Problem

#⭐️⭐️⭐️⭐️

House Robber III, 说现在houses是以binary tree的形式呈现, 小偷不能偷相邻的houses, 问最大的profit是多少?

#Solution

Dynamic Programming

dp[node] 表示以node为root的subtree, 最多能得到多少profit.

注意dp[node]和选不选node没有关系, 就是单纯的最优解.

因为碰到这种题可能第一反应会需要两个dp数组, dp_with[]和dp_without[]. 但是对于这道题来说, 一个数组就够了, dp[node]就是最优解, 无论选不选node. 比如下面这棵树:

1
2
3
4
5
6
7
2
\
1
/
0
\
5

如果要偷1, 那么2肯定就要跳过的. 但是至于偷不偷2的children, 比如0, 就不一定了. 根据这个例子, 显然不应该偷0而是应该偷5, 2 + 5 = 7 才是最终答案.

因此对于上面的tree, 在计算dp[node], node = 2的时候, 我们只要算 node.val + dp[node.right.left]即可.

1
2
3
4
5
6
7
8
9
10
11
12
13
int with = 1;
int without = 0;
if (node.left != null) {
with += dp[node.left.left] + dp[node.left.right];
without += dp[node.left];
}
if (node.right != null) {
with += dp[node.right.left] + dp[node.right.right];
without += dp[node.right];
}
dp[node] = Math.max(with, without);

#Code

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
27
28
29
30
31
32
class Solution {
public int rob(TreeNode root) {
if (root == null) return 0;
Map<TreeNode, Integer> dp = new HashMap<>();
dfs(root, dp);
return dp.get(root);
}
private void dfs(TreeNode root, Map<TreeNode, Integer> dp) {
if (root == null) return;
int with = root.val;
int without = 0;
if (root.left != null) {
dfs(root.left, dp);
with += dp.get(root.left.left) == null ? 0 : dp.get(root.left.left);
with += dp.get(root.left.right) == null ? 0 : dp.get(root.left.right);
without += dp.get(root.left);
}
if (root.right != null) {
dfs(root.right, dp);
with += dp.get(root.right.left) == null ? 0 : dp.get(root.right.left);
with += dp.get(root.right.right) == null ? 0 : dp.get(root.right.right);
without += dp.get(root.right);
}
dp.put(root, Math.max(with, without));
}
}

Comments