198. House Robber

Must take current house, no memory optimization

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        
        if len(nums) <= 2:
            return max(nums)
        
        dp = [0] * len(nums)
        # if len(nums) == 3: # either len(nums) == 3 or > 3, this dp[2] should be calculated.
        # dp[2] = max(nums[1], nums[0] + nums[2])  # 需要确定清楚 dp 的表示含义，既然我们定义 dp 为一定取当前 i 时的 max money，那么 dp[2] 只能为 nums[0] + nums[2]
        dp[0] = nums[0]
        dp[1] = nums[1]
        dp[2] = nums[0] + nums[2]
        
        for i in range(3, len(nums)):
            dp[i] = nums[i] + max(dp[i - 2], dp[i - 3])
            
        return max(dp[-1], dp[-2])

Must take current house, with memory optimization:

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        
        if len(nums) <= 2:
            return max(nums)
        
        # from collections import deque  # 用 deque 的话 dp[0], dp[1] 不好通过 index 获取，deque 只能先转换为 list 再用 index access，没个循环都做这个操作太费时
        # dp = deque()
        
        dp = [0] * 4
        dp[0] = nums[0]
        dp[1] = nums[1]
        dp[2] = nums[0] + nums[2]
        
        for i in range(3, len(nums)):
            # dp[i % 4] = nums[i] + max(dp[i % 4 - 2], dp[i % 4 - 3])
            dp[i % 4] = nums[i] + max(dp[(i + 4 - 2) % 4], dp[(i + 4 - 3) % 4])
            
        return max(dp[(len(nums) - 1) % 4], dp[(len(nums) - 1 + 4 - 1) % 4]) # 用节省空间的 memory efficient DP 方法会导致最终终止位置不在最后，需要通过 求余 来计算最终终止位置

Don't have to take current house, with memory optimization:

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        
        if len(nums) <= 2:
            return max(nums)
        
        dp = [0] * 3
        dp[0] = nums[0]
        # dp[1] = nums[1] # 我特么是不是个智障，都换了 dp 规则了，初始化最开始两个的时候也要考虑清楚规则的变化/运用
        dp[1] = max(nums[0], nums[1])
        
        for i in range(2, len(nums)):
            dp[i % 3] = max(dp[(i + 3 - 1) % 3], nums[i] + dp[(i + 3 - 2) % 3])
            
        # return dp[-1] # 用节省空间的 memory efficient DP 方法会导致最终终止位置不在最后，需要通过 求余 来计算最终终止位置
        return dp[(len(nums) - 1) % 3]