✅ DP

문제

링크

1. 문제 접근 및 해결 로직

점화식 자체를 문제에서 줬기 때문에 DP를 떠올리기 어렵지 않았다.

• 정의
  $f(n)$ : $n$번째 피보나치 수
• 구하는 답
  $f(n)$
• 초기값
  $f(0)=0$
  $f(1)=1$
• 점화식
  $f(n)=f(n-1)+f(n-2)(n>1)$

2. 코드

3. 시간 복잡도 분석

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

4. 문제에서 중요한 부분

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