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. 打家劫舍

已解答

中等

相關標簽

相關企業

你是一個專業的小偷，計劃偷竊沿街的房屋。每間房內都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。

給定一個代表每個房屋存放金額的非負整數數組，計算你?不觸動警報裝置的情況下?，一夜之內能夠偷竊到的最高金額。

三部曲

定義子問題

定義遞推關系

確定計算順序