개미 전사 (dp)

요구사항 숫자 n과 숫자 list가 주어질 때 최대 합을 구하여라. 제약 조건 인덱스의 값을 연속적으로 더할 수 없다. 1234567n = int(input())k = list(map(int, input().split()))dp = [k[0],k[1]] + [0]*(n-2)for i in range(2,n): dp[i] = max(dp[i-1], dp[i-2]+k[i]) print(dp[-1])cs 문제 해결의 접근 dp 문제이기에 우선 점화식을 찾기 위해 접근하였다.예제 입력 [1 3 1 5]를 보면 연속된 값을 갖지 못하기에 dp[0] = 1(k[0]), dp[1] = 3(k[1])으로 고정이 된다. 그리고 dp[2]에 올 수 있는 값은 k[1]을 갖는다면 k[2]는 가질 수 없고 k[0]를 갖는다면 k[2] 또한 가질 수 있다.이를 식으로 표현하면 dp[2] = dp[1] or dp[2] = dp[0] + k[2]..........

원문링크 : 개미 전사 (dp)