계단 오르기 문제

70. Climbing Stairs

문제

한번에 1단 혹은 2단으로 올라갈 수 있을 때, n단까지 오를 수 있는 모든 방법을 구하는 문제이다. 가장 기초적인 DP 문제이며 비슷한 문제로 타일링, 피보나치 문제 등이 있다.

테스트 케이스

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

풀이

1. 각 스텝을 오를 수 있는 방법의 수를 저장할n+1 크기의 배열 'dp'를 정의한다.
2. dp[i]는 단계 i로 올라가는 방법의 수이며, 초기값으로 1단계는 1(하나의 경우), 2단계는 2 (두가지 경우)로 설정한다. 입력값 n의 범위는 1 <= n <=45이기 때문에 최소 1
3. i 단계의 방법의 수는 이전 두 단계로 올라가는 방법의 수의 합과 같기 때문에 (현재 단계에 도달하기 위해 한 단계 또는 두 단계를 밟을 수 있기 때문) 초기값을 제외한 3 부터 n까지 반복하면서 i-1, i-2 값을 더해 준다.
4. 정상에 오르는 고유한 방법의 수를 나타내는dp[n]을 반환한다.

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
  const dp = new Array(n + 1)

  dp[1] = 1
  dp[2] = 2

  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }

  return dp[n]
};