[알고리즘] 동적 프로그래밍 (자바스크립트)

DP 동적 프로그래밍이란 복잡한 문제를 더 간단한 하위 문제의 모음으로 쪼갠 후, 각 하위 문제들을 풀어 그 답을 저장하여 문제를 해결하는 문제 해결 방식을 말한다. 적용 가능한 문제 영역이 그리 넓지 않지만, 적용 가능한 경우에는 성능에 있어 아주 큰 차이를 가져온다. 두 가지 특성 Overlapping Subproblems : 한 문제를 더 작은 문제들로 나눌 수 있고, 그 조각들 중 일부가 재활용 가능해야 한다. Optimal Substructure : 하위 문제의 최적 해답을 통하여 더 큰 범주를 갖는 문제의 최적 해답을 구성할 수 있어야 한다. 재귀를 통한 구현 : 피보나치 수열 수열의 첫 번째 숫자와 두 번째 숫자는 1이며, 그 밖의 경우 Fib(n) = Fib(n-1) + FIb(n-2)이다..

원문링크 : [알고리즘] 동적 프로그래밍 (자바스크립트)