house_robber.py

from typing import List


class Solution:
    """LeetCode #198 - House Robber (Medium)
    https://leetcode.com/problems/house-robber/

    Houses stand in a row with `nums[i]` money each. Robbing two adjacent houses
    triggers the alarm. Return the maximum you can take.
    """

    def rob(self, nums: List[int]) -> int:
        """Bottom-up DP with two rolling variables.

        Key insight: at each house there are exactly two options, and the best
        total is the better of them:

            rob it   -> its money + the best total up to house i-2
                        (i-1 is off limits, it is adjacent)
            skip it  -> the best total up to house i-1

            best(i) = max(best(i - 1), best(i - 2) + nums[i])

        Greedy fails here, which is worth being able to show: on [2, 1, 1, 2]
        taking the largest available first gives 2 + 1 = 3, while the answer is
        2 + 2 = 4. The DP considers both branches instead of committing early.

        Since the recurrence reaches back only two houses, two variables replace
        the whole table:

            prev = best total ending before the previous house  (i - 2)
            curr = best total up to the previous house          (i - 1)

        Both start at 0 - the empty prefix - which also makes the empty input
        return 0 with no special case.

        Time:  O(n) - one pass.
        Space: O(1)
        """
        prev, curr = 0, 0

        for money in nums:
            # rob this house (prev + money) or skip it (curr) - take the better
            prev, curr = curr, max(curr, prev + money)

        return curr