[알고리즘][Dynamic Programming] 징검다리 건너기

문제

철수는 학교에 가는데 개울을 만났습니다. 개울은 N개의 돌로 다리를 만들어 놓았습니다. 철 수는 돌 다리를 건널 때 한 번에 한 칸 또는 두 칸씩 건너뛰면서 돌다리를 건널 수 있습니다. 철수가 개울을 건너는 방법은 몇 가지일까요?

▣ 입력설명
첫째 줄은 돌의 개수인 자연수 N(3≤N≤45)이 주어집니다.
▣ 출력설명
첫 번째 줄에 개울을 건너는 방법의 수를 출력합니다.
▣ 입력예제 1 7
▣ 출력예제 1 34

풀이

풀이 자체는 어렵지 않았는데, 헷갈린 부분이 있었다.

function solution(n) {
  const dy = Array.from({length: n+2}, () => 0);
  dy[1] = 1;
  dy[2] = 2;
  for( i=3; i<=n+1; i++) {
    dy[i] = dy[i-1]+dy[i-2]
 }
	return dy[n+1]
}

solution(7)

간과했던 부분은,
'징검다리'가 7개라면 이 징검다리를 모두 건너 마지막 징검다리 다음 8번째 자리에 도착하는 방법의 수를 구해야 한다는 것이다.

따라서 출발점과 도착점까지 포함한 0 부터 8까지, 9개의 길이를 가진 배열에서 3번째 인덱스부터 방법의 수를 구해야 한다.
그 다음 마지막 7개의 징검다리를 모두 건넌 8번째, 즉 n=7이므로 n+1번째까지 방법의 수를 구하고 이것을 리턴해야 한다.