다이나믹 프로그래밍 문제접근

DP조건에 맞는지 확인하는 방법

 

1. 큰 문제를 작은문제로 나눌 수 있다.

2. 동일한 작은 문제를 반복적으로 해결한다.

 

 

 

처음에 딱 문제를 볼때 접근해야하는 과정

1. 그리디, 구현, 완전탐색인지 확인한다

2. 방법이 떠오르지 않으면 DP 조건을 확인해본다.

3. 재귀로 비효율적인 완전탐색을 구현해보고

4. 작은 문제로 큰 문제 해결이 가능하면 DP로 코드개선을 한다.

 

일반적인 코테의 DP문제는 기본유형으로 낸다.

= 점화식만 세우면 구현은 쉽다.