[알고스팟] 최대 증가 부분 수열 - 동적 계획, 최적해, 최적 부분 구조

※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 

 

최대 증가 부분 수열(링크)

각 원소로부터 출발한 재귀함수에서 해당 원소보다 뒤에 있는 원소 중 더 큰 것들만 골라 다시 재귀에 진입한다. 부분 수열을 가지고 재귀하지 않고 현재 Index 를 함수의 입력으로 한다.

 

즉, 현재 원소보다 큰 다음 원소의 Index 를 재귀로 입력한다. (다음에 선택될 원소는 항상 이전 원소보다 크므로 항상 모든 큰 값을 가지는 부분 수열을 재귀의 입력으로 줄 필요 없다.)

 

어떤 위치의 원소에 대해 다음으로 선택할 원소는 이전에 선택했던 원소와 관계없이 일정하므로 최적 부분 구조를 가지는 문제이다. (어떤 위치에서의 최적의 결과는 이전의 선택과 무관하게 일정.) 

 

따라서, 현재 함수에 진입하는 Index 에 대한 결과값만을 저장해서 Memoization하면 동적 계획으로 해결할 수 있다.

 

#include <iostream>
#include <vector>
using namespace std;

int len;
int cache[500];
vector<int> seq;

int lisMemoization(int start) {
    int& ret = cache[start];
    if (ret != -1) return ret;

    // lis starts from each element so they have minimum length of 1.
    ret = 1;
    for (int next = start + 1; next < seq.size(); ++next) {
        if (seq[start] < seq[next])
            ret = max(ret, lisMemoization(next) + 1);
    }

    return ret;
}

// LIS Starts from all of the index.
int startLIS() {
    int ret = 0;
    for (int i = 0; i < seq.size(); ++i) 
        ret = max(ret, lisMemoization(i));
    return ret;
}

int main() {
    int C; cin >> C;
    vector<int> answers;
     
    while (C-- > 0) {
        memset(cache, -1, sizeof(cache));

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

        answers.push_back(startLIS());
        seq.clear();
    }

    for (const auto& e: answers) cout << e << endl;

    return 0;
}