House Robber III

这道题就是把CLRS上面对于DP的递归定义搬上来就解开了，再利用Divide & Conquer的思维，首先每个节点选或者不选是两种情况，必须传一个参数进去判断当前是可以选择选或不选还是只能不选，另外需要一个哈希表备忘当前结果以防多次重复访问，这里注意两种状态的值要分别记录，下面是代码

class Solution(object):
    def rob(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        store = {}
        return self.DFS(root, True, store)

    def DFS(self, root, status, store):
        if not root:
            return 0

        if (root, status) in store:
            return store[(root, status)]

        result = 0
        a = self.DFS(root.left, True, store) + self.DFS(root.right, True, store)
        if status:
            b = root.val + self.DFS(root.left, False, store) + self.DFS(root.right, False, store)
            result = max(a, b)
            store[(root, True)] = result
            return result
        store[(root, False)] = a
        return a

这个题思路真的很奇怪很奇怪，虽然实际上，我们要考虑的就是两种情况，拿当前节点的情况下以它为根的子树的最大值，和不拿当前节点的情况下以它为根的子树的最大值记录下来，用哈希表备忘，最后一直上溯到根节点求得最后结果，思路非常类似于DP里面的记忆化搜索（某种程度上这就是记忆化搜索了）

class Solution(object):
    def rob(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        store = {1:{}, 0:{}}
        result = self.helper(root, 1, store)
        return result

    def helper(self, root, status, store):
        if not root:
            return 0

        if not root.left and not root.right:
            if status:
                return root.val
            return 0

        if root in store[status]:
            return store[status][root]

        if status:
            store[status][root] = max(self.helper(root.left, 0, store) + self.helper(root.right, 0, store) + root.val,
                        self.helper(root.left, 1, store) + self.helper(root.right, 1, store))
            return store[status][root]
        else:
            store[status][root] = self.helper(root.left, 1, store) + self.helper(root.right, 1, store) 
            return store[status][root]