70. Climbing Stairs

Problem

leetcode 바로가기

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

당신은 계단을 올라가고 있고, 정상에 도달하기 위해선 n만큼 올라가야 한다.

매번 당신은 한 계단 또는 두 계단을 올라갈 수 있다, 얼마나 많은 방법으로 정상에 올라갈 수 있을까?

Example 1:

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

Example 2:

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

Constraints:

• 1 <= n <= 45

Solution

var climbStairs = function(n) {
  if (n < 2) {
    return 1
  }

  return climbStairs(n - 1) + climbStairs(n - 2);
};
// 재귀로 풀 시 시간이 초과된다.

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
  if (n < 2) {
    return n
  }
  
  let a = 0,
  b = 1;
  
  for (let i = 0; i < n; i++) {
    let sum = a + b;
    a = b;
    b = sum;
  }
  
  return b;
};