337. House Robber III

Solution idea

树形DP

• 使用一个长度为2的数组，记录当前节点偷与不偷所得到的的最大金钱。所以本题dp数组就是一个长度为2的数组！

• Define DP: for any node, DP[0] = 记录不偷该节点所得到的的最大金钱; DP[1] = 录偷该节点所得到的的最大金钱。

• Base Case: 在遍历的过程中，如果遇到空节点的话，很明显，无论偷还是不偷都是0，所以就返回

• Recurrence:

  • 通过递归左节点，得到左节点偷与不偷的金钱。
  • 通过递归右节点，得到右节点偷与不偷的金钱。
  • 当前层：
    1. 如果是偷当前节点，那么左右孩子就不能偷，偷家总价值 = 左孩子不偷+右孩子不偷+当前层偷家的价值
    2. 如果不偷当前节点，那么左右孩子可以偷可以不偷，至于到底偷不偷一定是选一个最大的, 偷家总价值 = max(左孩子不偷, 左孩子偷) + max(右孩子不偷, 右孩子偷)
    • 当前层状态 = [偷家总价值case 2, 偷家总价值case 1]

• 整体机制：后序遍历+DP. 即，先拿到左、右孩子有什么，当前层再做点什么，就可以返回了

Time complexity = $O(n)$

个人经验教训

我一开始错误地理解了偷家机制：我以为层与层之间不挨着偷家就行。但题目意思是说不能偷直接相连的两个节点，所以，即使是挨着的两层，也有可能下一层的节点与上一层的节点没有直接相连。(e.g. 下一层最左子树的节点，上一层最右子树的节点: [2,1,3,null,4])

因为错误理解，我的解法用了层序遍历+DP: 层序遍历求出每一层的偷家价值总和， 再用DP. 然而，思路一开始就不对

Resource

代码随想录-337.打家劫舍 III