[알고리즘-JS] 동적 계획법 - 계단 오르기

문제

계단을 오를 때 한 번에 한 계단 또는 두 계단씩 올라간다. n개의 계단을 오르는 방법은 몇 가지인가?

 

입력 예제

7

 

출력 예제

21

 

 

 

 

풀이

function solution(n){  
  let answer=0;
  let dy = Array.from({length: n+1}, () => 0);
  dy[1] = 1; // 첫 번째 계단 가지수
  dy[2] = 2; // 두 번째 계단 가지수
  
  // 3 이상 계단 가지수 = 이전 두 계단 가지수를 더한 값
  for (let i = 3; i <= n; i++) {
    dy[i] = dy[i-2] + dy[i-1];
  }
  
  answer = dy[n];

  return answer;
}