House Robber
题意：
一个专业小偷打算去偷某条街上的房子，每个房子藏有一定量的金钱，不过相邻的房子间装有报警系统，所以如果你偷了两个相邻的房子，报警系统就会被激活，小偷就会被警察带走。现在要求你给小偷安排一个方案，让他能够偷到最多的钱，同时不被警察带走。
其实就是：给定一个非负数整数数组，求一个子序列a，要求序列中的元素在原数组互不相邻，求使得sum(a)最大的子序列a。
分析：
这个问题具有最优子结构性质，所以我们从头到尾遍历一次数组即可，注意：
- 每个房子有偷和不偷两个方案
- 如果偷了房子i，则房子i+1和房子i-1都不能偷
所以转移方程为，dp[i] 表示 房子 0~i 所能偷到的最大价值：
dp[i] = max(dp[i - 1] , dp[i - 2] + x[i])
边界是i - 1 < 0 和 i - 2 < 0 ，此时的dp 值为0
AC代码：
class Solution(object):
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 0:
return 0
dp = [0] * len(nums)
for (i, v) in enumerate(nums):
dp[i] = max(dp[i - 2] + v if i - 2 >= 0 else 0, dp[i - 1] if i - 1 >= 0 else 0, v)
return max(dp)House Robber II
题意：
在第一题的基础上，第一间房子和最后一件房子也是连着的，也就是说，房子构成了一个环。
分析：
构成环后，第一个房子和最后一个房子同时偷的情况是不被允许的，所以我们只能取其中一个。
假设把第一间房子从环上挖掉，就退化到了问题1，求出此时的价值为$V_1$
假设把最后一间房子从环上挖掉，就也退化到了问题1，求出此时的价值为$V_2$
那么答案就是两者中最大的那个。
AC代码：
class Solution(object):
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
if n == 0:
return 0
elif n == 1:
return nums[0]
no_0, no_n = self.lineRob(nums, 1, n), self.lineRob(nums, 0, n - 1)
return max(no_0, no_n)
def lineRob(self, nums, left = 0, right = 0):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
if n== 0:
return 0
elif n == 1:
return nums[0]
dp, left, right = [0] * n, max(left, 0), min(right, n)
for i in range(left, right):
v = nums[i]
dp[i] = max(dp[i - 2] + v if i - 2 >= left else 0, dp[i - 1] if i - 1 >= left else 0, v)
return max(dp)House Robber III
题意：
好了，小偷偷完那条街后，来到了一个新地方，他发现这个地方的房子布局是一个二叉树的结构，此时如果父亲和孩子节点同时被偷，报警系统就会被拉响。
分析：
跟第一题思路类似，每个节点有偷和不偷两种情况，从树底往上计算即可得到根节点的所得的最大值，所以我们需要做后序遍历，先计算两个孩子的 dp 值
AC代码：
每一个节点有两个状态，偷和不偷，这两个状态都对应有一个最大值，我用left[0] 表示左孩子不偷时，左孩子的最大值，left[1] 表示左孩子被偷时的最大值。那么对于父亲节点来讲：
- 如果父亲被偷，则孩子就不能被偷了，此时价值为
left[0] + right[0] + node.val - 如果父亲没被偷，则孩子偷不偷无所谓，只要价值最大就行，所以价值为
max(left) + max(right)
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def rob(self, root):
"""
:type root: TreeNode
:rtype: int
"""
res = self.tryRob(root)
return max(res)
def tryRob(self, node):
if not isinstance(node, TreeNode):
return [0, 0]
ans = [0, 0] # max value of (0 means not rob this node, 1 means rob this node)
left = self.tryRob(node.left)
right = self.tryRob(node.right)
ans[0] = max(left) + max(right)
ans[1] = left[0] + right[0] + node.val
return ans
