동적 계획법 (Dynamic Programming)

동적 계획법은 간단히 말해서 전에 사용했던 값을 재사용하는 것이다. 

주로 큰 문제에서 작은 문제로 분할되는 경우에 사용가능한데 분할정복이랑 다른 것은 중복이라는 개념이다. 

아직 동적 계획법에 대한 개념이 확실치 않아 위의 말이 정확히 무엇을 의미하는지는 모르지만 핵심 개념이 중복이라는 것은 확실하다.

그러나 동적 계획법은 전에 사용한 값들을 기록해둬야 하기 때문에 메모리의 문제가 생길수 있다는 단점이 있다. 

 

동적계획법은 크게 2가지 범주가 존재하는데

1. 하향식 접근방법인 메모이제이션

2. 상향식 방법인 타뷸레이션

이다.