✅ DP

문제

링크

1. 문제 접근 및 해결 로직

가능한 경우의 수는 다음과 같다.

1. 마지막 수를 포함하지 않음 (직전 수보다 작거나 같음)
2. 마지막 수를 포함 (직전 수보다 커야 함)

• 정의
  $f(n)$ : $n$ 자리까지에서의 가장 긴 증가하는 부분 수열
• 구하는 답
  $max(f(1),f(2),...,f(n))$
• 초기값
  $f(1)=1$
• 점화식
  $f(n)=f(n-1),(arr[n]<=arr[n-1])$
  $f(n)=f(n-1)+1,(arr[n]>arr[n-1])$

$n$ 자리까지 오기전에 가장 긴 부분 수열이 있을 수 있으므로
$f(n)$ 의 최댓값이 정답(수열의 가장 긴 증가하는 부분 수열의 길이)이다.

2. 코드

3. 시간 복잡도 분석

경우의 수를 모두 구하므로
$O(N)$

4. 문제에서 중요한 부분

DP문제는 점화식을 도출하는 것이 중요하다.
Bottm Up(반복문)으로 풀지 Top Down(재귀)으로 풀지는 선택사항