백준 가장 긴 증가하는 부분 수열 11053

문제 설명 : 주어진 수열 내에서 가장 긴 수열의 길이를 찾는 것이다.

문제내에서 주어진 것의 예시를 보겠습니다.

수열 A = {10, 20, 10, 30, 20, 50} 여기서 10, 20, 30 ,50되니 4이다

문제 풀이 :

여기서 점화식은
dp[idx] -> idx번째 원소의 값이 있는 위치에서 가장긴 수열의 길이이다.

이러한 점화식이 있을때 조건은
범위가 i = 1 ~ i < idx 일경우
i < idx && v[i] < v[idx] -> 가장 긴 부분수열이니 원소의 값도 더 작아야한다

중요 부분 소스

for (int i = 0; i < idx; i++) {
        if (i < idx && v[i] < v[idx]) {
            dp[idx] = max(solve(i) + 1, dp[idx]);
        }