동적 계획법을 이용하는 문제이다. 이 문제에는 총 세 가지의 규칙이 있다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 얼핏 보면, 움직일 수 있는 두개의 계단 중 큰 수를 가진 계단을 이용하는 문제로 볼 수 있다. 하지만, 이것은 탐욕 법을 이용한 문제 풀이이며, 해답이 아니다. 동적 계획법으로 모든 경우의 수를 살펴 보아야 한다. 연속하는 세 개의 계단을 밟을 수 없고, 마지막 계단은 무조건 밟아야 하기 때문에 배열을 이용하여 i번째 계단이 마지막이라 가정하고 하나씩 풀어 나가면..
