House Robber

Question

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.

Example Given [3, 8, 4], return 8.

Challenge O(n) time and O(1) memory.

问题分析

找最大什么的问题，而且是个序列跟前面的value有关，就是dp （但是 challenge解法怎么做？）

Thoughts

DP算法 dp[i]存到i为止能够获得的最大value

一开始我还很脑残的想dp[i]要对前0 to i-2个loop, 其实根本不需要，因为必然是一个递增的序列 dp[i] = max(dp[i-1], dp[i-2] + A[i])

Solution

class Solution:
    # @param A: a list of non-negative integers.
    # return: an integer
    def houseRobber(self, A):
        # write your code here
        if not A:
            return 0
        length = len(A)
        if length < 3:
            return max(A)
        dp = [0 for i in range(length)]
        dp[0] = A[0]
        if A[1] > A[0]:
            dp[1] = A[1]
        else:
            dp[1] = A[0]
        for index in range(2, length):
            dp[index] = dp[index-2] + A[index]
            if dp[index-1] > dp[index]:
                dp[index] = dp[index-1]

        return dp[length-1]