[백준 11055번] [동적 계획법] 가장 큰 증가 부분 수열

Approach

완전 탐색으로 이 문제를 처리한다고 하면 비둘기집의 원리에 따라서 중복되는 연산이 매우 많다는 사실을 쉽게 캐치할 수 있다.

dp[i] = i번째 수부터 시작하는 LIS 중 합이 가장 큰 값

dp[i] = max(v[i], max{dp[i + j] + v[i]}) for all j s.t v[i] < v[j]

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
vector<int> v;
int n;
int dp[1001];

int memoi(int k){
    int& ret = dp[k];
    if(ret != -1) return ret;
    int cmp = v[k];
    for(int i = k + 1; i < n; i++){
        if(v[k] < v[i]){
            cmp = max(cmp, memoi(i) + v[k]);
        }
    }
    return ret = cmp;
}


int main(void){
    fastio;
    memset(dp, -1, sizeof(dp));
    
    cin >> n;

    for(int i = 0; i < n; i++){
        int t;
        cin >> t;
        v.push_back(t);
    }

    int result = -1;
    for(int i = 0; i < n; i++){
        result = max(result, memoi(i));
    }

    cout << result << "\n";
    return 0;
}