LC 198.打家劫舍

关键：dp[i]的含义是考虑下标i及之前，能偷的最多的钱是多少，那么对于下标i 有 两种情况，偷或不偷 ， 这又依赖于前一个房间，和前前个房间是否被偷。若偷 i ， 那么dp[i] = dp[i-2] + nums[i] ;若不偷i ， dp 应保持为dp[i-1] , dp[i]取两者中的最大值。

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

JAVA版：

class Solution {public int rob(int[] nums) {if(nums.length == 1){ return nums[0];}if(nums.length == 0){ return 0;}int[] dp = new int[nums.length];dp[0] = nums[0];dp[1] = Math.max(nums[1] , nums[0]);for(int i = 2 ; i < nums.length ; i ++){dp[i] = Math.max(dp[i-2] + nums[i] , dp[i-1]);}return dp[nums.length - 1];}
}

LC 213.打家劫舍II

由于房间首尾是相连的，我们需要分三种情况考虑：

1.先不看首尾，考虑中间（考虑不包含首尾）

2.考虑包含首元素，不包含尾元素

3.考虑包含尾元素，不包含首元素

去这三种情况的最大值即可

tips：计算情况2和情况3的时候，实际上就包含了情况1，因此略去这个情况

class Solution:def rob(self, nums: List[int]) -> int:if len(nums) == 0:return 0if len(nums) == 1:return nums[0]result1 = self.robRange(nums, 0, len(nums) - 2)  result2 = self.robRange(nums, 1, len(nums) - 1)  return max(result1, result2)def robRange(self, nums: List[int], start: int, end: int) -> int:if end == start:return nums[start]prev_max = nums[start]curr_max = max(nums[start], nums[start + 1])for i in range(start + 2, end + 1):temp = curr_maxcurr_max = max(prev_max + nums[i], curr_max)prev_max = tempreturn curr_max