198. House Robber

[sophryu99]

198. House Robber

https://leetcode.com/problems/house-robber/

Memoization m[k] = money at the kth house p[k] = profit at kth house p[0] = 0, p[1] = m[1] p[k] = max(p[k-2] + m[k], p[k-3] + m[k])

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

        # Create a copy of the original nums array
        p = [0] * (len(nums) + 1)
        p[0] = 0
        p[1] = nums[0]
        p[2] = nums[1]
        for i in range(3, len(p)):
            p[i] = max(p[i - 3]+ nums[i - 1], p[i - 2] + nums[i - 1])

        return max(p)

n: array size

• Time complexity: O(n)
• Memory complexity: O(n)