동적 계획법

동적 계획법으로 풀 수 있는 문제는 반드시..

• 중복 부분 문제 구조 입니다.
• 최적 부분 문제 구조 입니다.
• 경우의수 부분문제 구조 입니다.

그게 뭔데.. (예시)

• 중복 부분 문제 구조 :
• 최적 부분 문제 구조 :
• 경우의수 부분문제 구조 :

DP 사고과정

1. 하향식 접근(재귀)
2. 상태공간 트리 작성
   • 중복 호출 파악, 공유 파악
3. 기저부터 상향식으로 접근
   • 뒤집어서 생각

DP 사고과정(상세)

1. 문제에 대한 이해, 정의 - 최적해?, 경우의 수?
2. 부분문제 식별
3. 부분문제에 대한 상태 표현(동적 테이블 설계 )
   • D[i], D[i][j]
   • i: 상태, D[i] : i상태일때의 값
4. 부분문제들간의 관계 파악 후 점화식 도출
   • D[i]가 D[i-1], D[i-2], .. 어떤 관계 ???
   • 관계 식별 후 더이상 관계를 이용한 해 도출이 안되는 기저 찾기
   • base case : 이때의 값 식별
5. 동적테이블 생성 및 base case 초기화 후 점화식을 활용해서 값 채우기
6. 해 도출
   • 마지막에 채워진 값이 무조건 해가 아니다 !!!
   • 문제에서 원하는 상태를 표현하고 있는 값들을 이용해서 해 도출
7. 필요시 공간복잡도 최적화