계단오르기(동적 프로그램)

코드

  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 - 1] + dy[i - 2];
    }

    answer = dy[n];

    return answer;
  }

해결 방법

이 문제는 동적으로 풀어야한다. 그러기 위해서는 점화식을 사용해야한다. 

먼저 1번 계단이랑 2번 계단은 올라가는 방법이 각각 1과 2인 것을 알 수 있다. 3번 계단은 (1번 계단)+(2번 계단)이고 4번 계단은 (2번 계단)+(3번 계단)이다. 따라서 점화식은 dy[n] = dy[n-1] + dy[n-2]라고 할 수 있다. 이런 원리로 문제를 해결할 수 있다.