题解 | 打家劫舍(二)

def rob(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]

    # 情况1：偷第一个房间，不偷最后一个房间
    dp1 = [0] * len(nums)
    dp1[0] = nums[0]
    dp1[1] = max(nums[0], nums[1])
    for i in range(2, len(nums) - 1):
        dp1[i] = max(dp1[i - 1], dp1[i - 2] + nums[i])

    # 情况2：不偷第一个房间，偷最后一个房间
    dp2 = [0] * len(nums)
    dp2[0] = 0
    dp2[1] = nums[1]
    for i in range(2, len(nums)):
        dp2[i] = max(dp2[i - 1], dp2[i - 2] + nums[i])

    # 返回两种情况的最大值
    return max(dp1[-2], dp2[-1])


# 输入处理
n = int(input())
nums = list(map(int, input().split()))
# 输出结果
print(rob(nums))