BOJ 1105

점화식 : DP[i] = MAX(DP[i], DP[i - j] + arr[i])

이유 : a개의 카드를 고를 때 나오는 가짓 수 : (a, a -1 /1, a - 2/ 2,....) 이기 때문에 모두 비교를 해야한다.

#include <iostream>

using namespace std;

long long dp[1000] = {};

int arr[1000];

int max(int a, int b){

    if(a > b) return a;

    else return b;

}

int main(){

    cin.tie(NULL);

    ios_base::sync_with_stdio(false);

    int N;

    cin >> N;

    for(int i = 1 ; i <= N; i++){

    int tmp = 0;

    cin >> tmp;

    arr[i] = tmp;

    }

    for(int i = 1; i <= N; i++){

        for(int j = 1; j <= i; j++){

            dp[i] = max(dp[i], dp[i - j] + arr[j]);

        }

    }

   cout << dp[N];

return 0;

}