Climbing Stairs

문제

Climbing Stairs

한번에 1칸 또는 2칸씩 계단을 오를 수 있는데, n단계까지 오르기 위해서는 총 몇가지 방법이 있는가?

뭐 이런 문제다.

풀이

• n = 1 경우 방법 1개

• n = 2 경우 방법 2개

• n = 3 경우 방법 3개

  • 1칸을 오르고 남은 1칸을 한번에 오르기 => 1칸 오르는 방법은 1개
  • 2칸을 오르고 남은 2칸을 한번에 오르기 => 2칸 오르는 방법은 2개

• n = 4 경우 방법 5개

  • 2칸을 오르고 남은 2칸을 한번에 오르기 => 2칸 오르는 방법은 2개
  • 3칸을 오르고 남은 1칸을 한번에 오르기 => 3칸 오르는 방법은 3개

• 즉, 중단 단계 값들을 이용해서 n단계의 값을 구할 수 있다.

• 점화식 f(n) = f(n-1) + f(n-2)

function climbStairs(n) {
  if (n <= 2) return n;

  // arr[0] = 1, arr[1] = 2
  const arr = [1, 2];
  for (let i = 2; i < n; i++) {
    arr[i] = arr[i - 1] + arr[i - 2];
  }
  return arr[n - 1];
}