https://www.acmicpc.net/problem/11052
11052번: 카드 구매하기첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)www.acmicpc.net
1.0번째 인덱스를 제외하고 n+1길이의 배열에 각각 p[i]값을 입력한다
l[4]를 예로 들자면
l[4] 현재 p[4]이므로
현재의 l[4]와 (l[3]+l[1]), (l[2]+l[2]), (l[1]+l[3]) 중의 최댓값이 l[4]가 된다.
이를 점화식으로 쓰면
l[i]=max( l[i],(l[i-1]+l[i]),(l[i-2]+l[2]),…..(l[i-n]+l[0]) ) 이다.
조금더 생각해보면
l[i-n]+l[n]은 l[n]+l[i]와 같은 결과를 가지므로
l//2+1 까지만 비교해줘도 답을 알수 있다.
n=int(input())l=[0]l+=(list(map(int,input().split())))for i in range(2,len(l)):
for j in range(1,i//2+1): l[i]=max(l[i],l[i-j]+l[j])print(l[n])