Leetcode 198. 打家劫舍

心路历程经典的动态规划题建模方法状态第i个房间是否被偷j(其实不用建模是否被偷可以隐含在状态转移里面去)动作偷 or 不偷返回值当前状态下获得的最高金额解法动态规划classSolution:defrob(self,nums:List[int])-int:nlen(nums)ifn0:return0ifn1:returnnums[0]dp[0for_inrange(n)]# 每间房无需建模偷与不偷dp[0],dp[1]nums[0],max(nums[0],nums[1])foriinrange(2,n):dp[i]max(dp[i-1],dp[i-2]nums[i])returndp[n-1] pythonclassSolution:defrob(self,nums:List[int])-int:nlen(nums)cachedefdp(i,j):# 代表以i结尾的房子偷或者不偷的状态下获得的最高金额ifi0andj1:returnnums[0]ifi0andj0:return0ifj0:returnmax(dp(i-1,0),dp(i-1,1))else:returndp(i-1,0)nums[i]returnmax(dp(n-1,1),dp(n-1,0))