unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 213: House Robber II

link

Dynamic Programming

Sub-problem

Say Rob(i) is the maximum money achievable by robbing the houses in nums[0...i]. Then:

\texttt{Rob}(i) = \max\left( \left\{ \texttt{Rob}(i-2)+\texttt{money}_i, \texttt{Rob}(i-1) \right\} \right).

Order

The directed graph is cyclic. To break the cycle, we do two passes. First pass robs first house and thus skips the last house. Second pass skips first house. We take the maximum of these two passes.

Time: \mathcal{O}(n), space: \mathcal{O}(n)

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 3:
            return max(nums)
        
        dp = [0] * n
        # rob 0-th
        dp[0], dp[1] = nums[0], nums[0]
        for i in range(2, n-1):
            dp[i] = max( dp[i-1], dp[i-2]+nums[i] )
        rob_zero_money = dp[n-2]
        
        # avoid 0-th
        dp = [0] * n
        for i in range(1, n):
            dp[i] = max( dp[i-1], dp[(i-2)%n] + nums[i] )
        avoid_zero_money = dp[n-1]

        return max(rob_zero_money, avoid_zero_money)

tanvirdotzaman

Leave a comment