337. House Robber III
2020-05-25 本文已影响0人
xxxcoder
key tips
动态规划
返回两个状态
algorithm 1
尝试动态规划
问题存在子问题结构，首先考虑动态规划
在从父节点向子节点传递状态的过程中，存在信息丢失和重复结算，可以考虑使用map保存局部计算结果
algorithm 2
动态规划 + 局部计算结果
algorithm 3
动态规划 + 多状态
robRoot(root)[0]: maximum value if root got not robbed
robRoot(root)[1]: maximum value if root got robbed
robRoot(root)[0] = max(robRoot(root.left)[0], robRoot(root.left)[1]) + max(robRoot(root.right)[0], robRoot(root.right)[1])
robRoot(root)[1] = root.val + robRoot(root.left)[0] + robRoot(root.right)[0]
