문제의 크기를 변화시켜 작은 문제의 결과를 이용해 큰 문제의 정답을 계산하는 알고리즘이다.
우선은 완전탐색으로 풀 수 있는지 확인하고, 시간을 줄일 때 다이나믹 프로그래밍 방법을 적용하는걸 고려해 보자.
1. 작은 문제 정의하기
전체 문제를 바탕으로 좀 더 쉽게 구할 수 있는 작은 문제를 정의한다.
2. 검증
작은 문제가 전체 문제를 해결할 때 도움이 되는지 확인한다.
3. 정의한 작은 문제를 해결할 때 사용되는 초기값을 설정하자.
몇 가지 값들은 쉽게 구할 수 있다.
4. 규칙을 찾아 점화식을 작성한다.
초기값을 이용해 값들의 규칙을 찾고, 이를 식으로 표현해 모든 값들에 대해 답을 얻는다.
5. 큰 문제 해결하기
여기서 점화식을 작성하는게 까다로운데.. 유형이 그렇게 다양하지 않다.
여러 문제를 풀어보고 문제 유형을 알아두면 다른 문제에 쉽게 적용할 수 있다.
점화식을 찾을 때 이전 항들과의 공통되는 부분을 생각하고, 특정한 규칙을 지정하면 어떻게 묶이는지에 집중해서 살펴보면 도움이 된다. (ex. 뭐로 시작하는지, 뭐로 끝나는지 등..)