[바킹독 알고리즘] 0x10강:다이나믹 프로그래밍

다이나믹 프로그래밍 (Dynamic Programming, DP)

: 여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘

위 사진과 같이 피보나치 수열을 DP를 이용해서 배열로 문제를 풀 수 있다.\

배열에 하위 값들에 대한 정보를 저장하고 있으면, 상위 문제를 풀 때 배열에 저장된 값을 이용해서 풀 수 있기 때문에 재귀보다 훨씬 수행시간이 줄어든다. 

DP를 푸는 과정

1. 테이블 정의하기

2. 점화식 찾기

3. 초기값 정하기