代码随想录刷题第四十八天| 198.打家劫舍 ● 213.打家劫舍II ● 337.打家劫舍III

代码随想录刷题第四十八天

今天是打家劫舍三部曲，最后一题树形dp有点难，其他还好

打家劫舍 (LC 198)

题目思路：

代码实现：

class Solution:
    def rob(self, nums: List[int]) -> int:
        dp = [0 for _ in range(len(nums)+1)]
        dp[1] = nums[0]

        for i in range(2, len(nums)+1):
            dp[i] = max(dp[i-1], nums[i-1]+dp[i-2])
        print(dp)
        return dp[len(nums)]

打家劫舍 II (LC 213)

题目思路：

代码实现：

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

    def robnoloop(self, nums):
        dp = [0 for _ in range(len(nums)+1)]
        dp[1] = nums[0]

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

打家劫舍 III (LC 337) 难想思路

题目思路：

代码实现：

class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        result0, result1 = self.traversal(root)
        return max(result0, result1)
        
    def traversal(self, node):
        if node is None:
            return (0,0)
        
        left0, left1 = self.traversal(node.left)
        right0, right1 = self.traversal(node.right)

        result0 = max(left0, left1)+max(right0, right1)
        result1 = node.val+left0+right0
        
        return result0, result1