-
Notifications
You must be signed in to change notification settings - Fork 461
Expand file tree
/
Copy path213_House_Robber_II.py
More file actions
34 lines (28 loc) · 1.05 KB
/
Copy path213_House_Robber_II.py
File metadata and controls
34 lines (28 loc) · 1.05 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# Iterative + 2 variables (bottom-up)
class Solution(object):
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
# The following 3 conditions are edge/special cases
if len(nums) <= 0:
return 0
elif len(nums) == 1:
return nums[0]
elif len(nums) == 2:
return max(nums)
include_1st_house = self.robHelper(nums, 0, len(nums) - 2)
exclude_1st_house = self.robHelper(nums, 1, len(nums) - 1)
return max(include_1st_house, exclude_1st_house)
def robHelper(self, nums, leftHouseNumber, rightHouseHumber):
previousRobbedMoney, currentRobbedMoney = 0, 0
for i in range(leftHouseNumber, rightHouseHumber + 1):
currentRobbedMoneyHolder = currentRobbedMoney
currentRobbedMoney = max(nums[i] + previousRobbedMoney, currentRobbedMoney)
previousRobbedMoney = currentRobbedMoneyHolder
return currentRobbedMoney
sol = Solution()
nums = [1,2,3,1]
out = sol.rob(nums)
print("Res: ", out)