class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # 使用动态规划，把之前的给保存起来
        ans=[0,nums[-1]]
        for i in range(1,len(nums)):
            ans.append(max(ans[-1],ans[-2]+nums[-1*i-1]))
        return ans[-1]

        # if len(nums)==0:
        #     return 0
        # if len(nums)==1:
        #     return nums[0]
        # if len(nums)>=2:
        #     return max(nums[0]+self.rob(nums[2:]),self.rob(nums[1:]))
        

198. 打家劫舍

已解答

中等

相关标签

相关企业

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

三部曲

定义子问题

定义递推关系

确定计算顺序