[DP] 개미전사

1. 문제 설명

- 개미가 배짱이네 집을 털러가는데 연속된 방을 털 수가 없다. 따라서 한 칸 을 넘어서 털어야 하는데 그럴 경우 가장 많이 털었을 때의 값을 묻는 문제

2. 코드

n = 4
array = list(map(int, "1 3 1 5".split()))
df = [0]*(n)

df[0] = array[0]
df[1] = max(array[0], array[1])
for i in range(2, n):
    df[i] = max(df[i-1], df[i-2]+array[i])
df[n-1]

# >> 8

3. 코멘트

- 항상 최선의 선택을 한다는 것을 알아둬야 한다.
- 이전의 선택에 대한 계산 정보는 해당 위치에 저장이 된다.
- 여기서 하나 신경써야할 점은 계산을 안하고 이전에 사용된 값을 그대로 사용해도 된다는 것이다. 왜냐하면 당장의 자리에서 계산을 해버리게 되면 추후에 있을 더 높은 값을 계산할 수 없어지기 때문이다.