leetcode-javascript
leetcode-javascript copied to clipboard
打家劫舍 |||-337
在上次打劫完一条街道之后和一圈房屋后,小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为“根”。 除了“根”之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫,房屋将自动报警。
计算在不触动警报的情况下,小偷一晚能够盗取的最高金额。
示例 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.
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/house-robber-iii 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
这题的题目上存在误导,并不是简单的跳一级去找最大值就可以,注意考虑这种情况:
2
/ \
1 3
/ \
n 4
这种情况下并不要跳级,而是第二层的 3 和第三层的 4 是去凑成打劫的最优解。
所以此题的解法是从顶层节点开始
- 抢劫当前的节点,那么儿子层就没法抢劫了,只能抢劫孙子层。
- 不抢劫当前节点,那么可以抢劫儿子层。
这两者对比求出的最大值,就是最优结果。
题解
自顶向下记忆化
let memo = new WeakMap()
let rob = function (root) {
if (!root) {
return 0
}
let memorized = memo.get(root)
if (memorized) {
return memorized
}
let notRob = rob(root.left) + rob(root.right)
let robNow =
(root.val || 0) +
(root.left ? rob(root.left.left) + rob(root.left.right) : 0) +
(root.right ? rob(root.right.left) + rob(root.right.right) : 0)
let max = Math.max(notRob, robNow)
memo.set(root, max)
return max
}
自底向上动态规划
上面的解法是自顶向下的,那么动态规划的自底向上解法应该怎么做呢?我们上一层的打劫最优解是依赖下一层的,所以显然我们应该先从最下层的求解。思考提取关键字「层序」、「自底向上」。
灵机一动,用递归回溯法配合BFS:
递归版的 BFS
先求出当前队列里所有的子节点,放入一个新的队列 subs
中,然后进一步 BFS
这个子节点队列 subs
。
那么这个递归 subs
之后的一行,就代表递归后回溯的时机,我们把「动态规划」求解的部分放在递归函数的后面, 当 BFS
到达了最后一层后,发现没有节点可以继续 BFS
了,这个时候最底层的函数调用慢慢弹出栈,从最底层慢慢往上回溯,
那么 「动态规划」求解的部分就是「自底向上」的了,我们在上层中求最优解的时候,一定能取到下面层的最优解。
/**
* @param {TreeNode} root
* @return {number}
*/
let rob = function (root) {
if (!root) return 0
let dp = new Map()
dp.set(null, 0)
let bfs = (nodes) => {
if (!nodes.length) {
return
}
let subs = []
for (let node of nodes) {
if (node.left) {
subs.push(node.left)
}
if (node.right) {
subs.push(node.right)
}
}
bfs(subs)
// 到达最底层后 最底层先开始 dp
// 再一层层回溯
for (let node of nodes) {
// 打劫这个节点
let robNow = node.val
if (node.left) {
robNow += dp.get(node.left.left)
robNow += dp.get(node.left.right)
}
if (node.right) {
robNow += dp.get(node.right.left)
robNow += dp.get(node.right.right)
}
// 不打劫这个节点 打劫下一层
let robNext = dp.get(node.left) + dp.get(node.right)
dp.set(node, Math.max(robNow, robNext))
}
}
bfs([root])
return dp.get(root)
}