점화식이란 인접한 항들 사이의 관계식을 의미한다. 즉 현재의 항이 이전의 항에 대한 식으로 표현할 수 있으면 이를 점화식이라고 한다. 대표적인 예로 피보나치 수열을 들면 다음과 같이 표현할 수 있다.

$a_{n+2} = f(a_{n+1}, a_n) = a_{n+1} + a_n, a_1 = 1, a_2 = 1$

이 피보나치 수열을 프로그래밍하면 다음과 같다.

#include <iostream>

using namespace std;

int fibo(int x) {
  if ((x == 1) || (x == 2)) {
    return 1;
  }
  return fibo(x - 1) + fibo(x - 2);
}

int main(void) {
  int n = 5; // 피보나치 수열에서 몇 번째 원소를 구하고 싶은지
  cout << fibo(n);

  return 0;
}

이는 재귀 함수를 이용하여 구현한 것인데 이렇게 작성하면 n이 커질수록 수행시간이 기하급수적으로 늘어나서 Overflow 될 수도 있다. 보통 이렇게 수행하게 되면 빅오 표기법으로 $O(2^N)$의 지수 시간이 소요된다.

따라서 이럴 때는 다이나믹 프로그래밍을 사용하면 효율적으로 해결할 수 있다. 보통 다음 조건을 만족할 때 사용할 수 있다.

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

피보나치 수열은 메모이제이션(Memoization) 기법을 사용해서 해결할 수 있다. 메모제이션은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 대, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다.

즉, 피보나치의 경우 점화식으로 구성되어 있기 때문에 재귀함수를 실행하게되면

1. f(6) = f(5) + f(4)
2. f(5) = f(4) + f(3)

2개의 식에서 f(5)를 2번 실행하게 된다. 메모이제이션은 f(5)의 값을 어딘가 저장해두고 불러와서 불필요한 연산을 줄이는 방법이다.