题解 | 打家劫舍(二)

import sys

# 22:30
# 和打家劫舍不同的是环形
# 分两种情况，如果第一家偷，那么最后一家不能偷，最大的为dp1(n-1)
# 如过第一家不偷，最大的为dp2(n),分为两种情况dp
# 第一家偷, 第二家不能偷，相当于从第三家开始dp + 第一家的钱
# 第一家不偷，相当于从第二家开始dp

n = int(input())

money = list(map(int, input().split()))

dp1 = [0] * (n+1) # 第一家偷, 第二家不能偷，相当于从第三家开始dp
dp2 = [0] * (n+2) # 第一家不偷，相当于从第二家开始dp

if n < 3:
    print(0)
else:
    dp1 = [0] * (n+1) # 第一家偷, 第二家不能偷，相当于从第三家开始dp, 并且最后最大值是dp[n-1]
    dp1[2] = money[0]
    dp1[1] = money[0]
    dp2 = [0] * (n+1) # 第一家不偷，相当于从第二家开始dp
    for i in range(2,n+1):
        if i>2:
            dp1[i] = max(dp1[i-1],dp1[i-2]+money[i-1])
        dp2[i] = max(dp2[i-1],dp2[i-2]+money[i-1])
    max_value = max(dp1[-2],dp2[-1])
    print(max_value)