DP(Dynamic Programing)

다이나믹 프로그래밍의 속성

1. Overlapping Subproblem

: 최초문제를 작은 문제로 쪼갤 수 있으며, 큰 문제와 작은 문제를 동일한 방법으로 풀 수 있다.

2. Optimal Substructure

: 문제의 정답을 작은 문제의 정답에서 도출할 수 있다.

작은 문제의 정답을 구했다면, 그 정답을 어딘가(배열)에 메모를 한다. : Memoization

다이나믹 프로그래밍의 풀이법

1. Top-down

작은 문제로 나눈다->작은 문제를 푼다->최초문제를 푼다

재귀호출

2. Bottom-up

크기가 작은 문제부터 차례대로 푼다->크기를 조금씩 키워가며 푼다->...->최초문제를 푼다