[DP] 백준 1965 상자넣기

처음에 ans = max(ans ... 부분을 for문을 안 돌리고 idx = 0 에서 시작하면 가장 큰 경우를 구할 수 있을 줄 알았다. 

하지만 idx >  0 에서 시작해서 더 큰 값을 구하는 경우가 존재한다. 

ex 

8 1 2 3 4 5 6 7 8 9 

idx = 0 부터하면 2

idx = 1 부터하면 9

#include <iostream>

#include <algorithm>

#include <cstring>

#include <limits.h>

#include <stack>

using namespace std;

int stb[10001]; // single table

int scache[100001]; // single cache

int tb[1001][1001];

int cache[1001][1001];

int n;

int go(int idx) {

       

       if (scache[idx] != -1) {

              return scache[idx];

       }

       int& ret = scache[idx] = 1;

       for (int i = idx+1; i < n; ++i) {

              if (stb[idx] < stb[i]) {

                     ret = max(ret,go(i) + 1);

              }

       }

       return ret;

}

int main(void) {

       memset(scache, -1, sizeof(scache));

       cin >> n;

       for (int i = 0; i < n; ++i) {

              cin >> stb[i];

       }

       int ans = 0;

       for (int i = 0; i < n; ++i) {

              ans = max(ans, go(i));

       }

       

       cout << ans;

       return 0;

}