[상태 정의를 통한 탐색] 계단 오르기 3

문제

OO이와 XX가 동시에 계단을 올라간다. 계단은 $n$칸. 둘 다 한 번에 1칸 또는 2칸을 오를 수 있다.

두 사람이 0번째 칸에서 출발해 동시에 $n$번째 칸에 도착하는 서로 다른 방법의 수를 구하라.

$n=3$이면

(1, 1), (2, 2), (3, 3)
(1, 1), (3, 3)
(1, 2), (3, 3)
(2, 1), (3, 3)
(2, 2), (3, 3)

로 5가지.