동적 계획법

DP :

하나의 큰 문제를 여러개의 작은문제로 분할하여 해결하는 방법

분할정복과 다르게 작은문제들의 답을 저장한 뒤 재활용

Top - Down, Bottom-Up

 

너무..빨라

 

1. 겹치는 부분문제

 

2. 최적부분구조

 

사용방법

1. DP로 풀수있는지 판단

2. 반복되는 부분문제찾기

3. 점화식 세우기

4. 기저상태 설정

5. 메모제이션 기법 적용(부분문제 값을 저장해서..ex. 1차원배열..2차원배열...)

6. 구현

 

예시)

돌게임2

 

 

..? 이해할 새도없었음