打家劫舍问题

打家劫舍问题

目录

1.198. 打家劫舍 - 力扣（LeetCode） (leetcode-cn.com)

2.213. 打家劫舍 II - 力扣（LeetCode） (leetcode-cn.com)

3.337. 打家劫舍 III - 力扣（LeetCode） (leetcode-cn.com)

---

1.198. 打家劫舍 - 力扣（LeetCode） (leetcode-cn.com)

 

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums)==0:return 0
        if len(nums)==1:return nums[0]
        dp=[0]*(len(nums))
        dp[0]=nums[0]
        dp[1]=max(nums[0],nums[1])
        for i in range(2,len(nums)):
            dp[i]=max(dp[i-1],dp[i-2]+nums[i])
        return dp[-1]

2.213. 打家劫舍 II - 力扣（LeetCode） (leetcode-cn.com)

连成环，说明第一个元素和最后一个元素可以看做相连

那么在这种情况下就分为两种情况：

（1）考虑第一个元素，不考虑最后一个元素，结果为result1

（2）考虑最后一个元素，不考虑第一个元素，结果为result2

取最大值即可

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums)==0:return 0
        if len(nums)==1:return nums[0]
        if len(nums)==2:return max(nums[0],nums[1])
        result1=self.robs(nums,0,len(nums)-2)
        result2=self.robs(nums,1,len(nums)-1)
        return max(result1,result2)

    def robs(self, nums: List[int],start:int,end:int) -> int:
        # if start==end:return nums[start]
        dp=[0]*(len(nums))
        dp[start]=nums[start]
        dp[start+1]=max(nums[start],nums[start+1])
        for i in range(start+2,end+1):
            dp[i]=max(dp[i-1],dp[i-2]+nums[i])
        return dp[end]

3.337. 打家劫舍 III - 力扣（LeetCode） (leetcode-cn.com)

采用后序遍历的方法，对于每个节点都返回一个元组，第一项为不考虑这个节点考虑它的左右孩子

第二项为考虑这个节点不考虑它的左右孩子

class Solution:
    def rob(self, root: TreeNode) -> int:
        result=self.robs(root)
        return max(result)

    #后序遍历
    def robs(self, root: TreeNode) -> int:
        if root==None:
            return (0,0)
        left=self.robs(root.left)
        right=self.robs(root.right)

        cur=root.val+left[0]+right[0]
        notcur=max(left[0],left[1])+max(right[0],right[1])
        return (notcur,cur)