문제2 x 1, 1 x 2 타일로 2 x n 짜리 타일을 채우는 방법의 수를 물어보고 있다. 이 문제를 푸는 핵심은 우리가 이전에 구했던 경우의 수 들로 다음 경우의 수를 구해야 하는 것이다. 전 항과 우리가 구하려고 하는 항의 관계를 흔히 점화식이라고 부른다.다이나믹 프로그래밍 문제를 푸는 데의 핵심은 점화식을 구하는 것에 있다. n=1 부터 초반 몇 개 항을 적다 보면, 항들 간의 관계를 생각해볼 수 있는데, 우리가 2 x k 짜리 타일을 채우는 방법을 고민할때, 2 x k 타일을 채우는 경우의 수는 2가지밖에 없다. 2 x (k-1) 짜리 타일에 1 x 2 타일을 마지막에 붙이거나, 2 x (k-2) 짜리 타일에 2 x 1 타일 2개를 2 x 2로 만들어서 붙이는 것이다. 결국 2 x n 짜리 타일..