代码随想录算法训练营day47| 198. 打家劫舍、213. 打家劫舍II、337. 打家劫舍III

198、打家劫舍：

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

比较简单的动态规划问题

213、打家劫舍II：

class Solution(object):
    def rob_nums(self, nums):
        n = len(nums)
        dp = [0] * n
        dp[0] = nums[0]
        if n == 1:
            return dp[0]
        dp[1] = max(nums[0], nums[1])
        for i in range(2, n):
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
        return dp[n - 1]

    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 1:
            return nums[0]
        nums_start = nums[:-1]
        nums_end = nums[1:]
        return max(self.rob_nums(nums_start), self.rob_nums(nums_end))

前题的变种，考虑到第一个和最后一个不能共存，可以划分为两种情况，取最大的

337、打家劫舍III：

class Solution(object):
    def rob_tree(self, cur):
        if not cur:
            return [0, 0]
        left_dp = self.rob_tree(cur.left)
        right_dp = self.rob_tree(cur.right)
        value_notrob = max(left_dp[0], left_dp[1]) + max(right_dp[0], right_dp[1])
        value_rob = cur.val + left_dp[0] + right_dp[0]
        return [value_notrob, value_rob]

    def rob(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        vals = self.rob_tree(root)
        return max(vals[0], vals[1])

有点难度，关键是要想到使用后序遍历，把底层的节点状态一层层往上转移，和普通的动态规划给个数组的解法不同，要深刻理解递归和树的遍历

原文地址：https://blog.csdn.net/zwq54argfun/article/details/136394626

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！