#11052 카드 구매하기

# 문제

# 입력 및 출력

# 풀이

dp[n] = max(dp[0]+dp[n], dp[1]+dp[n-1], dp[2]+dp[n-2], ... , dp[n-1]+dp[1])

중복되는 값은 있지만 간단한 반복문으로 구현하기 위해 그냥 위의 식으로 풀었음

#include <iostream>
#include <algorithm>
using namespace std;
int dp[1001];

int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> dp[i];
	}
	for (int i = 1; i <= n; i++) {
		int maxv = dp[i];
		for (int j = 1; j < i; j++) {
			maxv = max(maxv, dp[j] + dp[i - j]);
		}
		dp[i] = maxv;
	}
	cout << dp[n];
}