You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

思路

这道题就相当于是给定一个一维数组，不能访问连续的两个元素，还要保证取到的元素之和最大。

我们考虑利用动态规划的方法来做。

首先确定最基本的问题，我们假设街道里的房子放在nums数组里。如果街道里没有房子，或者只有一栋房子，最大值当然是空值或者唯一值。而如果街道里有两栋房子，取收益最大的那栋即可。

现在考虑三栋房子的情况。假设我们已经知道了前两栋房子的最大收益，现在将第三栋房子加入考虑。如果取到了第三栋房子，那么第二栋房子就不能取。所以我们能够得到的最大值，就是nums[1]与nums[3]之和与nums[2]之间的最大值。

如果加入第四栋房子，其实情况也是一样的，我们能够得到的最大值，是nums[2]与nums[1]的最大值，加上nums[4]的值——与nums[3]，也就是第三栋房子的时候取到的最大值之间，所得到的最大值。

这样一来，我们就建立了一个可以一直往下寻找的问题，推出了问题的解决方法。

现在我们需要开一个新的空间来存储我们得到的最大值。直觉上来说，我们就利用一个一维数组，就可以记录这些值。一维数组的每一项，都对应着我们从左到右遍历到该元素之前可以达到的收益最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        median = []
        length = len(nums)
        if (length <= 0):
            return 0
        elif (length == 1):
            return nums[0]
        elif (length == 2):
            return max(nums[0], nums[1])
        else:
            median.append(nums[0])
            median.append(max(nums[0], nums[1]))
            for i in range(2,length):
                median.append(max(nums[i] + median[i-2], median[i-1]))
            return median[length-1]

http://xiadong.info/2016/11/leetcode-198-house-robber/

http://bookshadow.com/weblog/2015/04/01/leetcode-house-robber/