题解 | #打家劫舍(二)#

还是dp，只是相较于没有首末次约束的情况下多了一个思维过程而已。由于不能同时偷首末家，因此一共有三种可能：偷最多的钱要么是1.偷了首家，不偷末家，要么是2.偷了末家，不偷首家，要么是3.首末家都没偷。因此可以做两个dp向量，一个dp不包括首家，一个dp不包括末家，最后返回两者较大者即可。

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return int整型
#
class Solution:
    def rob(self , nums) -> int:
        # write code here
        dp1 = [0] * len(nums)  # 包含首家,不包含末家
        dp2 =[0] * len(nums)   # 包含末家,不包含首家
        for i in range(len(nums)):
            if i == 0:
                dp1[0] = nums[0]
            elif i==1:
                dp1[1] = max(nums[0] , nums[1])
                dp2[1] = nums[1]
            else:
                dp1[i] = max(dp1[i-2] + nums[i] , dp1[i-1])
                dp2[i] = max(dp2[i-2]+nums[i] , dp2[i-1])
        return max(dp1[-2] , dp2[-1])

nums = [1,3,6]
print(Solution().rob(nums))