leetcode_198. 打家劫舍

超出时间限制
class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        if len(nums)==1:
            return nums[0]
        if len(nums)==2:
            return max(nums[0],nums[1])
        for i in range(2,len(nums)):
            return max(nums[0]+self.rob(nums[2:]),self.rob(nums[1:]))

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        if len(nums)==1:
            return nums[0]
        ls=[]
        ls.append(nums[0])
        ls.append(max(nums[0],nums[1]))
        for i in range(2,len(nums)):
            ls.append(max(ls[i-1],nums[i]+ls[i-2]))
        return ls[len(ls)-1]