House Robber

LeetCode 198

Finite-state machine

class Solution:
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        """
        [2,7,9,3,1]
        
        Draw a finite state machine.
        1. 要注意每個state的初始狀態很重要!
        2. 轉移也要注意 s[i] = max(s[i-1] ...) or s[i-1]+ t[i]
        3. 最後值的位置
        """
        if not nums:
            return 0
        profit = 0
        s0 = [0]*len(nums)
        s1 = [0]*len(nums)
        s0[0] = 0
        s1[0] = nums[0]
        for i in range (1, len(nums)):   
            s1[i] = s0[i-1] + nums[i]
            s0[i] = max(s0[i-1], s1[i-1])
        return max(s0[-1], s1[-1])