DP, 다이나믹 프로그래밍

DP 의 조건 두 가지,

1) 최적 부분 문제가 존재하는가?
2) 반복되는 하위 문제가 있는가?

1번 조건을 해결하는 방법은 DP 외에도 다양한 방법이 있어 100%라 보기는 어렵고,
그렇다 보니 2번 조건이 필요한거지 않을까 싶다.

결국 최종 해를 구하는 과정에서 지속적으로 반복적인 결과값을 사용하느냐를 고민해봐야 한다.

[피보나치 수열]

예시로 많이 등장하는 피보나치 수열을 보자.
우리가 구하려는 fibo(n)의 값은 결국 이전 값들의 누적으로 완성된다.

그럼 DP는 어떻게 쓰는 것일까?
일단, 문제를 읽고 반복되는 부분이 있는지 먼저 파악해야 한다.
(이걸 점화식으로 칭함)

알고리즘 문제를 풀다보면 이 부분이 제일 어려운데,
끝내 고민하고 구글링해보면 나만 점화식을 못 세우는 거 같다...;

그리고, 반복적인 결과값을 어떻게 저장할 것인지 고민한다.

1) 하향식 방식

const fibo = (number, memo=[]) => {
  if(memo[n]!==undefined) return meno[n];
  if(n<=2) return 1;
  let res = fibo(n-1, memo) + fibo(n-2, memo);
  memo[n] = res;
  return res;
}

2) 상향식 방식

const fibo = (number) => {
	if(n<=2) return 1;
    let result = [0,1,1]
    for(let i = 3; i<=n; i++){
    	result[i] = result[i-1] + result[i-2]
    }
    return result[i];
}

피보나치 수열에 대한 설명은 생략하겠습니다.

코드를 보면 알겠지만, 구하려는 숫자에서부터 내려오는지
아래에서부터 올라가는지에 대한 차이가 있습니다.
(다만, 재귀를 쓰면 시간 복잡도에서 대부분 실패하기 때문에 다른 방식을 지향)

DP는 이렇다할 공식이나 그런게 없어서,
문제를 봤을 때 어떤 부분이 반복되고(점화식)
어떤 방식으로 결과를 도출하는게 편한지 파악하는게 중요한 것 같다