동적 프로그래밍

재귀만 사용할때 계산방식

같은 결과의 계산을 한다.

1. 메모이제이션

재귀 함수를 사용한다.

/** 메모리제이션 */
const fibonacci2 = (n, memo) => {
  if(n == 0 | n == 1) return n;

  if(memo[n] == null) {
    memo[n] = fibonacci2(n - 2, memo) + fibonacci2(n - 1, memo);
  }

  return memo[n];
}

장점

재귀 덕분에 하향식 계산 방식으로 어려운 문제를 간단하게 해결할 수 있다.

단점

속도가 빠른 대신 메모리를 사용한다.

2. 타뷸레이션

/** 타뷸레이션 */
const fibonacci3 = (n) => {
  if(n <= 1) return n;

  let table = [0, 1];

  for(let i = 2; i <= n; i++){
    table[i] = table[i - 2] + table[i - 1];
  }

  return table[n];
}

상향식 계산 방식으로 계산에 필요한 모든 값을 전부 계산 후 테이블에 저장 해둔다.