打劫房屋

LeetCode题目思路
时间复杂度O(n)，空间复杂度O(n)

def houseRobber(self, A):
        # write your code here
        # 状态方程f(n) = max(f(n-1),f(n-2)+f(n))
        # f(n)走到当前位置，偷到的最多钱（最优状况）
        # 和走楼梯问题相关,和斐波那契数列类似

        if len(A) == 0:
            return 0
        
        f = [0] * len(A)
        
        #初始条件
        f[0] = A[0]
        if len(A) > 1:
            f[1] = A[1]
        
        #状态方程
        for index in range(2,len(A)):
            f[index] = max(f[index-1],f[index-2]+A[index])
            
        return f[len(A)-1]

时间复杂度O(n)，空间复杂度O(0)，借原有数组存储，缺点改变了A数组

def houseRobber(self, A):
        if len(A) == 0:
            return 0
        
        for index in range(2,len(A)):
            A[index] = max(A[index-1],A[index-2]+A[index])
            
        return A[len(A)-1]

借用求斐波那契数列可知，其实这题只需要保存f(n)之前的两个数f(n-1)和数f(n-2)即可
时间复杂度O(n)，空间复杂度O(1)

def houseRobber(self, A):
        f, g, f1, g1 = 0, 0, 0, 0
        for x in A:
            f1 = g + x
            g1 = max(f, g)
            g, f = g1, f1
       
        return max(f, g)