1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
Map<TreeNode, Integer[]> memo = new HashMap<>();
public int rob(TreeNode root) {
return Math.max(dfs(root, 0), dfs(root, 1));
}
private int dfs(TreeNode node, int canRob) {
if (node == null) {
return 0;
}
if (memo.containsKey(node) && memo.get(node)[canRob] != null) {
return memo.get(node)[canRob];
}
int max = Integer.MIN_VALUE;
if (canRob == 1) {
max = Math.max(max, dfs(node.left, 0) + dfs(node.right, 0) + node.val);
}
max = Math.max(max, dfs(node.left, 1) + dfs(node.right, 1));
memo.putIfAbsent(node, new Integer[2]);
memo.get(node)[canRob] = max;
return max;
}
}
|
这个是recursion + memoization. 这应该是我们首先想到的答案. 也就是如何把big problem分解成subproblem. 开始的root如果抢, 那么就要知道两个child不抢的时候最大值是多少加在一起, 再加上root的val即可. 如果不抢, 就要知道两个child可以抢的前提下的最大值了, 两个加载一起即可. 因此递归函数的功能我们就确定下来, 也就是我们想知道的东西. 我们想知道从某个node开始如果抢能抢到的最大值是多少, 如果不抢, 能抢到的最大值是多少. 于是递归函数的两个parameters就确定了, 也就是代表某个tree的node以及此时能否抢. 注意是能否而不是必须.
也就是给递归函数一个node, 以及能不能抢的条件, 它就能告诉我们在此条件下, 从该node开始最多能抢多少. 这就好办了. 我们到一个node. 如果是null, 那就返回0, 说明一点儿也抢不到. 如果不是, 就看自己此时能不能抢, 如果能抢, 那就是分两种情况: 抢还是不抢. 如果抢, 那么就看两个child(如果有的话)不抢的前提下的最大值加在一起在加上自己的val即可. 如果不抢, 那么就看两个child不抢的前提下的最大值加一起即可. 如果此时的node不能抢, 那么还是看两个child在能抢的前提下的最大值.
recursion的搭档就是memoization. 于是我们需要这个. 我们记录的就是某个node在能抢或者不能抢的前提下的能抢到的最大值. 于是用个map, key就是node, value则是一个int array. 我们之所以声明Integer array是为了区分开一种情况是否走过和确实就是0. 如果是int[], 那么初始值就是0. 这样无法区分这种情况是走过了得到了0, 还是没有走过初始化是0.
时间复杂度: O(n)
空间复杂度: O(n)
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 {
Map<TreeNode, Integer[]> memo = new HashMap<>();
public int rob(TreeNode root) {
dfs(root);
return Math.max(memo.get(root)[0], memo.get(root)[1]);
}
private void dfs(TreeNode node) {
if (node == null) {
return;
}
if (node.left == null && node.right == null) {
memo.put(node, new Integer[] { 0, node.val });
return;
}
dfs(node.left);
dfs(node.right);
memo.put(node, new Integer[2]);
if (node.left == null) {
memo.get(node)[0] = Math.max(memo.get(node.right)[0], memo.get(node.right)[1]);
memo.get(node)[1] = memo.get(node.right)[0] + node.val;
} else if (node.right == null) {
memo.get(node)[0] = Math.max(memo.get(node.left)[0], memo.get(node.left)[1]);
memo.get(node)[1] = memo.get(node.left)[0] + node.val;
} else {
memo.get(node)[0] = Math.max(memo.get(node.left)[0], memo.get(node.left)[1])
+ Math.max(memo.get(node.right)[0], memo.get(node.right)[1]);
memo.get(node)[1] = memo.get(node.left)[0] + memo.get(node.right)[0] + node.val;
}
}
}
|
DP的解法. 受到recursion + memoization的启发. 我们记录的是某个node, 抢的话以该node为tree的最大值能抢多少以及不抢的话以该node为tree的最大值能抢多少. 于是这就是状态. 那么我们要从base case开始走. base case就是leaf node. 此时我知道leaf node不抢的话以该node为root的tree抢的最大值就是0, 抢的话以该leaf node为root的tree抢的最多的就是node.val.
然后我们leaf node之上的node就可以利用这个subproblem的答案来去构建它的答案. 递归的逻辑就是如果此时不抢, 那么就是两个child node(如果有的话)可以抢的前提下的最大值. 如果此时抢, 那么就是两个child node不抢的前提下的最大值相加再加上当前node的val. 于是此时用dp解的话, 构建当前node的状态的话也是两种, 抢或者不抢. 如果抢的话, 那就需要两个child node不抢的前提下的最大值. 不抢的话就看左边node是抢的得到最大还是不抢得到最大, 取最大的. 右边一样. 于是dp转移方程就是以上叙述的了.
其实这道题能想到也是因为做了clone graph中返回时给结果的思路. 我们遍历node用post order遍历. 那到了leaf node的时候, 肯定就能确定它的两个状态. 然后返回, 再继续post order, 直到某个node下面的所有node都遍历完后, 它此时的两个状态也就可以确定了.
时间复杂度: O(n)
空间复杂度: O(n)
