2.20 알고리즘4 DP

큰 문제를 작은 문제로 나누어서 해결?
1) DP - 중복 가능한 작은 문제
2) 분할 정복 (Divide And Conquer) - 작은 문제 중복 불가능

Dynamic Programming 동적 계획법

1. Overlapping Subproblem : 겹치는 작은 문제
   ex.피보나치 수
   N0 = 0, N1 = 1
   N n = N n-2 + N n-1 (n >= 2)

   문제: N번째
   작은 문제: N-1 + N-2

   문제: N-1번쨰
   작은 문제: N-2 + N-3

2. Optimal Substructure : 문제의 정답이 작은 문제로 해결
   ex. 서울에서 가장 빠른 길
   서울-대전-대구-부산
   대전 대구 부산
   -> 문제 크기에 상관없이 어떤 한 문제의 답은 일정함

같은 문제는 정답이 일정하므로, 한 문제는 한 번만 풀어서 메모해두고 사용한다. -> Memoization

//함수의 깊이 N일때 시간복잡도 O(2^N)
const fibonacci = (n) => {
  if(n<=1){
  	return n
  } else {
  	return fibonacci(n-1) + fibonacci(n-2)
  }
}

//모든 문제를 한번씩 풀어서 memoization -> 문제의 개수 * 문제 1개 푸는 시간 = N * 1  시간복잡도O(N)
const fibonacci = (n) => {
  if(n<=1){
  	return n
  } else {
    if(memo[n] > 0) {
    	return memo[n]
    }
  	memo[n] = fibonacci(n-1) + fibonacci(n-2)
    return memo[n]
  }
}

다이나믹 구현 방식

O(N)
1)top-down 재귀
2)bottom-up

const bottomup = (n) => {
  d[0] = 0;
  d[1] = 1;
  for(i = 2; i < n; i ++) {
    d[i] = d[i-1] + d[i-2]
  }
  return d[n]
}