[Algorithm]Dynamic Programming

다이나믹 프로그래밍은 이미 계산된 결과는 별도의 메모리 영역에 저장하여
다시 계산하지 않도록 하는 것으로 시간 복잡도를 줄이는 방법이다.

func(n)의 값을 구하기 위하여 func(n-1), func(n-2)의 값이 필요한 경우를 예로 들 수 있으며,
알려진 유형으로는 피보나치 수열이 있다.

func(n)의 값을 구하기 위하여 n이전의 결과값들이 필요한데,
이전의 값들을 배열로 저장하는 것으로 중복된 연산을 줄일 수 있다.

⚠️자료구조에서 사용되는 Dynamic과 DP의 Dynamic은 같은 의미가 아니다.

---

예시 문제: 멀리 뛰기

문제의 n번째 값을 나열하면 아래와 같다.

n      result
-------------
1        1
2        2 
3        3
4        5
5        8
6       13
(중략)

나열한 값을 토대로 정리한 값들의 관계성은 아래와 같다.

n      result
-------------
1      1
2      1 + 1
3      2 + 1
4      3 + 2
5      5 + 3
6      8 + 5
(중략)

따라서 예시 문제는 n번째의 답을 구하기 위하여
n-1, n-2번째의 값이 필요하기 때문에
이를 배열에 저장하여 중복된 계산을 실행하지 않을 수 있다.

//풀이 코드

const fibonacci = (n) => {
  const dp = new Array(n+1).fill(0);
  dp[0] = 1; dp[1] = 1;
  
  for(let i = 2; i <= n; i++)
    dp[i] = (dp[i-1] + dp[i-2]) % 1234567;
  
  return dp[n];
}