[LeetCode] 70. Climbing Stairs (Easy) 풀이

❓ 문제

You are climbing a staircase. It takes n steps to reach the top.
계단을 올라가야한다. 계단 끝에 도달하기 위해 n 계단을 밟아야한다.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
한번에 1계단 또는 2계단만 올라갈 수 있다. 계단 마지막으로 올라가기 위해서 중복 없이 얼마나 많은 경우의 수가 있는가?

 

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

❗ 풀이

결국 못 풀어서 인터넷을 찾아보았다...

 

전형적인 DP(Dynamic Programming) 문제라고 되어있었다!
DP(Dynamic Programming)은 더 공부하여 나중에 블로그에 올리려고 한다.

간단하게 살펴보면, DP는 

/**
 * @param {number} n
 * @return {number}
 */
 var climbStairs = function(n) {
  let dp = [];
  dp[0] = 1;
  dp[1] = 1;
  
  for(let i = 2; i <= n; i++) {
      dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
};

Runtime: 68 ms
Memory Usage: 42.1 MB

🚩 Detail

• 날짜 : 2022.06.30
• 난이도 : Easy
• 제목 : Climbing Stairs
• URL :  https://leetcode.com/problems/climbing-stairs/