LeetCode 房间盗窃house_robber(Python

Record my own stupidity. 20200530
whispering：too hard

问题描述：
偷盗相邻的house会触发警报，求解在不触发警报的情况下可以偷盗的最大价值。（跟粉刷房子的问题类似）
问题设定：
给定数组house_values:代表每个house内可偷盗的价值，value in values非负。

本问题可以使用暴力解法，穷举所有偷盗的可能性，并记录每种情况所有偷的价值即可。这里不进行赘述，主要记录DP求解。

DP问题的三个步骤
1.问题分解（将问题分解为重复子问题）
2.状态定义（为问题设定有效的状态）
3.DP方程（状态转移方程，求解第i个子问题与其他子问题的相关关系）

使用二维DP问题的求解方式，使用二维数据不仅记录当前状态的最大值，还需要记录当前house是否被偷。数组size为n*2

def house_robber(values):
    """
    input:
    values: house values
    return:
    res: the max value
    """

    # boundary check
    if not values:
        return 0
    if len(values) == 1:
        return values[-1]

    # state define (2 dims) size = n*2  
    # 0: not steal  1: steal 
    a = [[0]*2 for _ in range(len(values))]
    a[0][0] = 0
    a[0][1] = values[0]

    for i in range(1,len(values)):
        a[i][0] = max(a[i-1][0], a[i-1][1])
        a[i][1] = a[i-1][0] + values[i]

    return max(a[-1][0], a[-1][1])

为了降低空间复杂度，使用一维数组进行问题简化，记录当前状态i对应的house能获得的最大value，取出最大值。

def house_robber_(values):
    """
    input:
    values: house values
    return:
    res: the max value
    """
    # boundary check
    if not values:
        return 0
    if len(values) == 1:
        return values[-1]
    if len(values) == 2:
        return max(values[0], values[1])

    # state define (1 dim) size = n*1
    a = values # (state init)
    a[1] = max(values[0], values[1])

    for i in range(2,len(values)):
        a[i] = max(a[i-2] + values[i], a[i-1])
    return a[-1]

观察两种求解的DP方程，可以看出状态i的推导，只跟状态i-1和i-2有关。因此，有大佬仅使用两个状态值得转换就可以完成本问题的求解。

def rob(values):
    """
    input:
    values: house values
    return:
    res: the max value
    """
    # boundary check
    if not values:
        return 0
    if len(values) == 1:
        return values[-1]
    if len(values) == 2:
        return max(values[1], values[0])


    pre_ = values[0]
    # 对于状态的定义是 当前所在位置可以偷盗的最大值
    cur_ = max(values[1], values[0])

    for i in range(2,len(values)):
        tmp = max(pre_+values[i], cur_)
        pre_ = cur_
        cur_ = tmp

    return cur_

house_robber_2:假设数组的收尾相连，那么对于数组的考虑就不能从现有的思路考虑，也就是数组被分为两个部分，取头不取尾values[:-1]，或者取尾不取头values[1:]。代码的话跟上面类似，这里只给出利用第三种方式的解法。

def rob(values) :
    """
    input:
    values: house values
    return:
    res: the max value
    """
    # boundary check
    if not values:
        return 0
    if len(values) == 1:
        return values[-1]
    if len(values) == 2:
        return max(values[1], values[0])
    if len(values) == 3:
        return max(max(values[0],values[1]),max(values[1],values[2]))

    pre_0 = values[0]
    # 对于状态的定义是 当前所在位置可以偷盗的最大值
    cur_0 = max(values[1], values[0])

    pre_1 = values[1]
    # 对于状态的定义是 当前所在位置可以偷盗的最大值
    cur_1 = max(values[1], values[2])


    for i in range(2,len(values)):
        if i == 2:
            tmp = max(pre_0+values[i], cur_0)
            pre_0 = cur_0
            cur_0 = tmp
        elif i == len(values)-1:
            tmp = max(pre_1+values[i], cur_1)
            pre_1 = cur_1
            cur_1 = tmp
        else:
            tmp_0 = max(pre_0+values[i], cur_0)
            pre_0 = cur_0
            cur_0 = tmp_0
            tmp_1 = max(pre_1+values[i], cur_1)
            pre_1 = cur_1
            cur_1 = tmp_1

    return max(cur_0,cur_1)