打家劫舍 |||-337

[sl1673495]

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

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

示例 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 是去凑成打劫的最优解。

所以此题的解法是从顶层节点开始

1. 抢劫当前的节点，那么儿子层就没法抢劫了，只能抢劫孙子层。
2. 不抢劫当前节点，那么可以抢劫儿子层。

这两者对比求出的最大值，就是最优结果。

题解

自顶向下记忆化

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)
}