问题描述：

一个小偷去一个街区偷东西，求偷得价值最大，唯一限制就是不能偷连续的两家，因为这样会触发警报。

建模：

给定一个列表，里面存着每家可以偷的价值，输出最大偷到的价值。

思路：动态规划

如果输入是v1v2...vm，用S[i]表示从v1v2...vi能偷到的最大价值。

递归子问题：S[i] = max(S[i-1], vi + S[i-2])

初如条件：S[0] = 0 S[1] = v1 S[2] = max(S[1], v2 + S[0])

代码：Python

class Solution:    # @param num, a list of integer    # @return an integer    def rob(self, num):        n = len(num)        if n == 0:            return 0        elif n == 1:            return num[0]        else:            s = [0 for i in range(n)]            s[0] = num[0]            s[1] = max(num[0], num[1])            for i in range(2,n):                s[i] = max(s[i-1], s[i-2] + num[i])            return s[n-1]