198. House Robber
Approach 1: Keeping track of amount robbed using DP
class Solution(object):
def rob(self, nums):
"""
https://leetcode.com/problems/house-robber/description/
:type nums: List[int]
:rtype: int
"""
lea = len(nums)
if lea == 0:
return 0
if lea == 1:
return nums[0]
if lea == 2:
return max(nums)
if lea == 3:
return max(nums[0] + nums[2], nums[1])
dp = [0] * lea
dp[0], dp[1], dp[2] = nums[0], nums[1], nums[0] + nums[2]
for i in range(3, lea):
dp[i] = nums[i] + max(dp[i-2], dp[i-3])
return max(dp[-1], dp[-2])
Here we keep track of the max sum from position 0 to i
in dp[i]
. This is calculated as follows dp[i] = nums[i] + max(dp[i-2], dp[i-3])
Moreover the initial conditions are dp[0]
, dp[1]
and dp[2]
which are initalised as nums[0]
, nums[1]
and nums[0] + nums[2]
respectively.
In the end we only have to check the last two entries to see which one is greater and return the larger one.
Time Complexity: O(N)
Space Complexity: O(N)
Last updated