美文网首页
LeetCode 房间盗窃house_robber(Python

LeetCode 房间盗窃house_robber(Python

作者: 掉了西红柿皮_Kee | 来源:发表于2020-05-30 17:51 被阅读0次

    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-1i-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)
    

    相关文章

      网友评论

          本文标题:LeetCode 房间盗窃house_robber(Python

          本文链接:https://www.haomeiwen.com/subject/vqhhzhtx.html