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

把打家劫舍二的问题分解为两种情况,可以按打家劫舍一的问题求解。

1.偷了第一家，没偷最后一家（相当于只遍历到倒数第二家的位置）

2.没偷第一家，偷了最后一家（相当于初始值为0，遍历到最后的位置）

分治的思想，原问题的答案可以分解为两个子问题的求解。

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

        # 没偷第一家，遍历到最后一位
        for i in range(l):
            if i == 0:
                dp2.append(0)
            elif i == 1:
                dp2.append(nums[i])
            else:
                dp2.append(max(nums[i] + dp2[i - 2], dp2[i - 1]))
                
        print(dp1, dp2)
        return max(dp1[-1], dp2[-1])