DP
对于第(i)个状态（房子），有两种选择：偷（rob）、不偷（not rob）
递推公式为：
(f(i)=max
\begin{cases}
\begin{cases}
{f(i-1)+val_i,}&{rob_{i-1}==0} \
{f(i-2)+val_i,}&{rob_{i-1}==1}
\end{cases}
& \text{rob}\
f(i-1), & \text{not rob}
\end{cases}
)
(f(i))为动态规划表（DP表）（状态(i)下的最优解）
(val)为每间房子里的钱（val表）
(rob)为记录是否已经偷过，0表示没偷过，1表示偷了（is_robbed表）。
有了递推公式代码就很好写了
class Solution:
# @param {integer[]} nums
# @return {integer}
def rob(self, nums):
val=[0]+nums
DP=[0]*(len(nums)+1)
is_robbed=[0]*(len(nums)+1)
for i in range(1,len(val)):
if is_robbed[i-1]==0:
f_rob=DP[i-1]+val[i]
else:
f_rob=DP[i-2]+val[i]
f_no_rob=DP[i-1]
if f_rob>f_no_rob:
DP[i]=f_rob
is_robbed[i]=1
else:
DP[i]=f_no_rob
is_robbed[i]=0
return DP[len(nums)]