✅ DP

문제

링크

1. 문제 접근 및 해결 로직

바로 직전의 수에 따라 $n$번째 원소를 감소하는 부분 수열에 포함 할 수 있는지 없는지 결정된다.

1. 바로 직전의 수보다 작다면, 직전 수 까지의 가장 긴 감소하는 부분 수열의 길이 + 1이고
2. 바로 직전의 수보다 크거나 같다면, 직전 수 까지의 가장 긴 감소하는 부분 수열의 길이가 현재 수 까지의 가장 긴 감소하는 부분 수열의 길이다.

• 정의
  $f(n)$ : $n$ 번째 원소까지 가장 긴 감소하는 부분 수열의 길이
• 구하는 답
  $max(f(1),f(2),...,f(n))$
• 초기값
  $f(1)=1$
• 점화식
  $f(n)=f(n-1)+1,(arr[n]<arr[n-1])$
  $f(n)=f(n-1),(arr[n]>=arr[n-1])$

$n$ 까지 오기전에 가장 긴 감소하는 부분 수열이 존재할 수도 있으므로
$f(1)$~$f(n)$의 최댓값이 구하는 답이다.

2. 코드

3. 시간 복잡도 분석

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

4. 문제에서 중요한 부분

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