《剑指offer》面试题89:房屋偷盗

"""
题目:输入一个数组表示某条街道上的一排房屋内的财产数量。如果这条街道上相邻的两幢房屋被盗就会触发报警系统,请计算小偷在这条街道上个最多能偷多少财产。
例如:街道上5幢房屋内的财产用数组[2,3,4,5,3]表示,如果小偷到下标为0、2、4的房屋内盗窃,那么他能偷到价值为9的财物,这是他能偷到的最多的财物。

分析:
首先考虑递归关系,即元素间的推导关系。
    假设站到第5个元素上,那么它的最大值,应该是max( dp(数组,备忘录,3), dp(数组,备忘录,2) ) + 数组[5]的值。
    索引4不用考虑,因为会触发报警系统。而是否要考虑索引1呢?如果要偷索引1,那么必然可以顺带偷索引3,因此考虑到索引2就行了。
然后考虑递归出口,
   由于按照上面的推导关系,第i个元素依赖第i-1和第i-3的值,而当i-3小于0时,就会触发异常,因此i小于3时的场景都要给出递归出口。
     
"""
def dp(houses,result_map,i):
    if i == 0:
        return houses[i]
    if i == 1:
        return max(houses[0],houses[1])
    if i == 2:
        return houses[0]+houses[2]
    else:
        if i in result_map:
            return result_map[i]
        else:
            max_value = max(dp(houses,result_map,i-2),dp(houses,result_map,i-3))+houses[i]
            result_map[i] = max_value
            return max_value
def steal_houses(houses):
    result_map = {}
    length = len(houses)
    max_value = max(dp(houses,result_map,length-1),dp(houses,result_map,length-2))
    print(max_value)

houses = [2,3,4,5,3]
steal_houses(houses)


上一篇:二分(二)供暖器


下一篇:CF56E Domino Principle(BIT+dp)