[코테 알고리즘] 동적계획법(Dynamic Programming)과 피보나치 수열

동적계획법(Dynamic Programming)의 전제와 정의

---

⚠️ 큰문제를 동일한 형태의 작은문제로 나눌 수 있어야 한다.
⚠️ 작은문제에서 구한 값이 그것을 포함하는 큰문제에서도 동일하다.
.
하나의 문제는 단 한번만 풀도록 하는 알고리즘을 말한다.
그러기 위해서 이미 구한 답을 잠시 기록해두는 과정을 '메모이제이션'이라고 한다.

🕑 시간복잡도: O(N)

동적계획법(Dynamic Programming)과 피보나치 수열

---

❓ 피보나치 수열이란
: 모든 항이 바로 앞 두 항의 합인 수열을 말한다.
(단, 첫번째항과 두번째항은 1 이다)

import java.util.*;

class Main {
  static int[] A = new int[100];
  public static void main(String[] args) {
    System.out.println(dp(30));
  }

  public static int dp(int x) {
    if(x == 1) return 1;
    if(x == 2) return 1;
    if(A[x] != 0) return A[x]; // 메모이제이션
    return A[x] = dp(x-1) + dp(x-2); // 큰 문제를 동일한 형태의 작은 문제로 나눈다
  }
}