algorithms/houseRobbers.py at master · fafk/algorithms · GitHub

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
"""
You are a professional robber planning to rob houses along a street. Each house has a certain amount
of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses
have security system connected and it will automatically contact the police if two adjacent houses
were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the
maximum amount of money you can rob tonight without alerting the police.


Example 1:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
             Total amount you can rob = 2 + 9 + 1 = 12.

"""
from typing import List


class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums) - 1
        mnem = [float("-inf")] * (n + 1)
        highest = float("-inf")

        if n == -1:
            return 0

        for i, num in enumerate(reversed(nums)):
            current_ind = n - i
            if i == 1 or i == 0:  # last or one before last
                current_max_profit = mnem[current_ind] = num
            else:
                current_max_profit = mnem[current_ind] = max(mnem[current_ind + 2:]) + num
            highest = max(highest, current_max_profit)

        return highest


assert Solution().rob([2, 3, 4, 3]) == 6
assert Solution().rob([3, 1, 2, 50]) == 53
assert Solution().rob([2, 7, 9, 3, 1]) == 12