House Robber

力扣198、213

Posted by songjiu on May 20, 2019

题目概述

关于力扣打家劫舍问题的整理。该系列题型就是给定一个代表房屋价值的list,通过限定不能rob 相邻房屋来计算最终最大的利益是多少。

House Robber I

题目概述

题目分析

动态规划,共两种情况:1. rob i号房子,那么总收益为 i号 加上 i-2 的最大收益 (因为最短隔一间房子)2. 不rob i号房子,总收益为 i-1 的最大收益。因此只要比较1.2两种方式的大小,就可以确定到第i个房子的时候的最大收益。 当房子数小于等于3个的时候,单独判断。。。(其实这里应该是只需要房子数小于等于2单独判断)

代码

def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums)==0:
            return 0
        elif len(nums)==1:
            return nums[0]
        elif len(nums)==2:
            return max(nums[0],nums[1])
        elif len(nums)==3:
            return max(nums[1],nums[0]+nums[2])#前三种单独判断
        else:#房子多于三所的时候,dp
            dp=[0]*len(nums)
            dp[0]=nums[0]
            dp[1]=max(nums[0],nums[1])
            dp[2]=max(nums[1],nums[0]+nums[2])
            for i in range(3,len(nums)):
                dp[i]=max(nums[i]+dp[i-2],dp[i-1])
            return dp[-1]

House Robber II

题目概述

题目分析

该题目与1的区别为强行说第一个房子和最后一个房子也算相邻,一开始的想法是使用一个list记录当前的dp有没有受到第一家房子的影响,再判断到最后一个房子,但是这存在两个问题:
1.当rob当前房子 与 不rob当前房子的利益相同的时候,究竟是使用带有第一家房子的方案还是不使用,无法方便计算。
2.加入房子1以后,即使选取了最后一个房子没有受到第一个房子的直接影响,也有可能在比较大小的过程中间接影响(比如由于房子1的加入,本来应该选A线路,而改编成为B线路,即使B当中没有房子1的参与。
综上,了解了一下其他人的大多数做法,就是将包含房子1不包含最后一个房子的组合,与不包含房子1但是包含最后一个房子的组合分别求极值。

代码

def getmax(self,nums,dp):
        if len(nums)==0:
            return 0
        for i in range(len(nums)):
            if i==0:
                dp[i]=nums[i]
            elif i==1:
                if nums[0]>nums[1]:
                    neighbor=[0,1]
                dp[i]=max(nums[0],nums[1])
            else:
                dp[i]=max(dp[i-1],nums[i]+dp[i-2])
        #print(dp)
        return dp[-1]
    def rob(self, nums: List[int]) -> int:
        #nums=[1,1,3,6,7,10,7,1,8,5,9,1,4,4,3]
        if len(nums)==0:
            return 0
        if len(nums)==1:
            return nums[0]
        dp=[0]*(len(nums)-1)
        #print(self.getmax(nums[1:],dp1),self.getmax(nums[:-1],dp2),self.getmax(nums[1:len(nums)-2],dp3))
        return max(self.getmax(nums[1:],dp),self.getmax(nums[:-1],dp))