House Robber I & II

题目描述

II

首尾不能都抢，那我们分别将首尾去掉，各自算一遍最大值，再取其中的最大值 就可以了。

解题方法

Solution

第一遍写的DP

• dp[i][0] 表示不包含i
• dp[i][1] 表示包含i

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        length = len(nums)
        if length == 1:
            return nums[0]
        if length == 2:
            return max(nums[0], nums[1])

        dp = [[0 for j in range(2)] for i in range(length)]
        dp[0][1] = nums[0]
        dp[1][0] = nums[0]
        dp[1][1] = nums[1]

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

        return max(dp[length-1][0], dp[length-1][1])

global vs local的写法 house robber II

local[i] 表示包含i global[i] 表示到i为止的最大值

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        length = len(nums)
        if length == 1:
            return nums[0]

        return max(self.rob1(nums[:-1]), self.rob1(nums[1:]))

    def rob1(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        length = len(nums)
        if length == 1:
            return nums[0]
        if length == 2:
            return max(nums[0], nums[1])

        localDP = [0 for i in range(length)]
        globalDP = [0 for i in range(length)]
        localDP[0] = nums[0]
        globalDP[0] = nums[0]
        localDP[1] = nums[1]
        globalDP[1] = max(nums[0], nums[1])

        for i in range(2, length):
            localDP[i] = globalDP[i-2] + nums[i]
            globalDP[i] = max(localDP[i], localDP[i-1])

        return globalDP[length-1]

Reference