[동적계획법][JS] 계단오르기

동적계획법이란?

문제의 범위를 쪼개어 범위 안에서의 답을 찾아 저장해두고,
범위를 넓혀가며 좁은 범위에서 구했던 답을 이용해 점진적으로 답을 찾아가는 것

문제

철수는 계단을 오를 때 한 번에 한 계단 또는 두 계단씩 올라간다.
만약 총 4계단을 오른다면 그 방법의 수는 5가지이다.
총 N계단일 때 철수가 올라갈 수 있는 방법의 수는 몇 가지인가?

첫째 줄은 계단의 갯수인 자연수 N(3<=N<=45)가 주어집니다.
첫번째 줄에 올라가는 방법의 수를 출력합니다
입력예제
7
출력예제
21

풀이

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

Reference

• 인프런 - 자바스크립트 알고리즘 문제풀이