엔지니어 게시판
LeetCode 솔루션 분류

# [Easy - wk3 - Q2] 70. Climbing Stairs

• Chloe 작성
• 작성일

• 636 조회
• 4 댓글

### 본문

70. Climbing Stairs

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?

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`

댓글 4

## Jack님의 댓글

• Jack
• 작성일
python

Time Limit Exceeded

``````class Solution:
def climbStairs(self, n: int) -> int:
if n == 1:
return 1
if n == 2:
return 2
return self.climbStairs(n-1) + self.climbStairs(n-2)``````

*** Memoization ***
Runtime: 32 ms, faster than 83.88% of Python3 online submissions for Climbing Stairs.
Memory Usage: 13.8 MB, less than 58.27% of Python3 online submissions for Climbing Stairs.

``````class Solution:
dp = collections.defaultdict(int)

def climbStairs(self, n: int) -> int:
if n <= 2:
return n

if self.dp[n]:
return self.dp[n]

self.dp[n] = self.climbStairs(n-1) + self.climbStairs(n-2)
return self.dp[n]
``````

*** Tabulation ***
Runtime: 60 ms, faster than 9.43% of Python3 online submissions for Climbing Stairs.
Memory Usage: 13.9 MB, less than 58.27% of Python3 online submissions for Climbing Stairs.

``````class Solution:
def climbStairs(self, n: int) -> int:
dp = collections.defaultdict(int)
dp[1]=1
dp[2]=2

for i in range(3, n+1):
dp[i]=dp[i-1]+dp[i-2]
return dp[n]``````

## mingki님의 댓글

• mingki
• 작성일
C++
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Climbing Stairs.
Memory Usage: 5.8 MB, less than 83.45% of C++ online submissions for Climbing Stairs.
``````class Solution {
public:
int climbStairs(int n) {
int curr = 1, prev = 0;
for (int i = 1; i <= n; ++i) {
curr += prev, prev = curr - prev;
}
return curr;
}
};``````

## dawn27님의 댓글

• dawn27
• 작성일
Runtime: 77 ms, faster than 47.02% of JavaScript online submissions for Climbing Stairs.
Memory Usage: 42 MB, less than 34.99% of JavaScript online submissions for Climbing Stairs.
``````var climbStairs = function(n) {
let counterFunc = (stairsRemaining, savedResult) => {

if (stairsRemaining < 0) return 0;
if (stairsRemaining === 0) return 1;

if (savedResult[stairsRemaining]) return savedResult[stairsRemaining];

savedResult[stairsRemaining] = counterFunc(stairsRemaining-1, savedResult) + counterFunc(stairsRemaining-2, savedResult);

return savedResult[stairsRemaining];
}

return counterFunc(n, {});
};``````
전체 128 / 1 페이지

### 새댓글

• 등록자 JakeMinSVK 등록일 18:25
• 등록자 JakeMinSVK 등록일 18:24
• 등록자 학부유학생 등록일 06.22
• 등록자 학부유학생 등록일 06.21
• 등록자 Coffee 등록일 06.21
• 등록자 Coffee 등록일 06.21
• 등록자 SVKOREANS 등록일 06.20
• 등록자 학부유학생 등록일 06.20
• 등록자 Coffee 등록일 06.20
• 등록자 키위 등록일 06.20

### Stats

• 현재 접속자 77 명
• 오늘 방문자 653 명
• 어제 방문자 683 명
• 최대 방문자 1,262 명
• 전체 회원수 264 명