알고리즘을 세울 때 상당히 어려운 것이 다양한 조건의 점화식을 구성하는 것이다.

점화식이란 수열의 각각의 항들간 관계를 표현한 식이다.

---

점화식 조건

1. 동일한 부분문제로 큰 문제를 분해하는 것이 가능하다.
2. 가장 작은 단위의 해답 base(기저식)이 존재한다는 점이다.

알고리즘의 관점

base와 동일 부분 문제를 활용해서 문제를 다루게 되면 중복으로 해결하는 동일부분 문제를 없앨 수 있다.

즉 시간복잡도 면에서 상당히 중요한 개념이다.

점화식을 프로그래밍 언어로 다루면 아래와 같이 짝지을 수 있다.

수학	프로그래밍
부분 문제	상태
베이스	종료조건
점화식	점화식(함수)

주로 컴퓨터에서는 재귀함수를 활용해 이런 문제들을 다룬다. 이를 통해 중복계산을 제거하는 DP 프로그래밍을 시도해 볼 수 있다.

코딩테스트에서의 접근법 (재귀함수 세우기)

1. 먼저 해당 문제를 재귀함수로 풀어야하는지 판단한다.
   동일한 부분문제로 나눌 수 있어야하며, 이를 활용해서 푸는 것이 중복계산을 얼마나 유효하게 줄일 수 있는지 또는 구현하기에 적합한지를 근거로 한다.

2. ✨유효하다면 재귀정의 구성요소 3가지를 세워야한다.

이름	프로그래밍 관점	설명
상태	재귀함수의 매개변수	각 부분문제가 문제 해결에 필요로 하는 입력값
종료조건	재귀함수의 종료 조건	가장 작은 부분문제의 단위
점화식	재귀함수의 연산	전체 문제를 부분 문제로 분해해서 연산

3. 중복계산을 제거할 수 있다면, 제거
   여기서부턴 DP 프로그래밍의 영역이며, 시간복잡도를 개선하기 위한 작업이다. 위의 상태에 따른 결과를 재활용하는 방식으로 중복계산을 제거한다.