baekjoon 11053:가장 긴 증가하는 부분 수열

baekjoon 11053 가장 긴 증가하는 부분 수열

11053번 가장 긴 증가하는 부분 수열

접근

간단한 well-known dp 문제이다. lis문제.

코드

#include <iostream>
#include <vector>
#include <array>
using namespace std;
array<int, 1001> cache;
int dp(int n, vector<int>& v);
int main(){
  int n; cin >> n;
  vector<int> v(n+1);
  for(int i = 1; i < n+1; i++){
    cin >> v[i];
  }
  v[0] = 0;
  fill(cache.begin(), cache.end(), -1);
  cout << dp(0, v)-1;
  return 0;
}
int dp(int n, vector<int>& v){
  if(n == v.size()-1){
    return 1;
  }
  if(cache[n] != -1){
    return cache[n];
  }
  int& ret = cache[n];
  ret = 1;
  for(int i = n+1; i < v.size(); i++){
    if(v[i] > v[n]){
      ret = max(ret, dp(i, v)+1);
    }
  }
  return ret;
  
}

배운 점

dp연습