동적 프로그래밍 (DP) 해결 방법

동적 프로그래밍 (DP) 해결 방법

 

Step 1 : n이 가장 작을 때부터 하나하나 그려가보면서 규칙성을 찾는다
Step 2 : 규칙성이 보이기 시작하면 일반화하고, 점화식을 구한다.
Step 3 : 탑다운 or 바텀업 중 좀 더 편한 방법으로 구현 (물론 연습할 때는 둘 다 해보기)

---

 

 

탑다운의 필수 요구사항, 바텀업의 필수 요구사항 꼭 숙지하기

 

 

 

탑 다운 필수요구사항

1. 값이 한없이 작아지는 것을 방지하기 위한 탈출조건 (n이 0이거나 1 정도에서 return 하고 끊는 조건이 필요)
2. memoization (시간 초과 방지)
3. 과거의 상태값을 불러올 때는 인덱스를 이용한 배열 직접 접근보다는 재귀함수를 이용한다. Example) dp[n-1] (X) => solve(n-1) (O)

 

바텀 업 필수요구사항

1. n이 가장 작을 때부터 시작하는 것이니까, 초기값을 설정한다.
2. 과거의 상태값을 불러올 때는 반복문과 인덱스를 이용한 배열 직접 접근을 이용한다. Example) dp[n-1]