프로그래머스: 도둑질

연이은 값을 선택할 수 없는 문제는 전형적인 DP 문제로 많이 접해보았을 것이다.

다만 이 문제는 첫 번째 값과 마지막 값을 동시에 선택할 수 없다는 조건이 추가되어있다.

이에 따라, 첫 번째 값을 선택가능한 case와 마지막 값을 선택 가능한 case로 나누어 그 중 최댓값을 return한다.

1) 0th idx ~ (n-1)th idx

2) 1th idx ~ (n)th idx

def solution(money):
    dp1 = [0] * (len(money) - 1)
    dp1[0] = money[0]
    dp1[1] = max(money[0], money[1])
    for i in range(2, len(money)-1):
        dp1[i] = max(dp1[i-2]+money[i], dp1[i-1])
    
    dp2 = [0] * len(money)
    dp2[0] = 0
    dp2[1] = money[1]
    for i in range(2, len(money)):
        dp2[i] = max(dp2[i-2]+money[i], dp2[i-1])
        
    return max(dp1[-1], dp2[-1])