[LeetCode] 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

반응형

---

주어진 숫자를 1과 2의 더하기 조합으로 만드는 경우의 수를 구하는 문제이다.

기존 0과 1인 경우 1을 출력하는 것으로 조건을 건다.

전체 리스트를 0으로 세팅 후 index 0과 1의 값을 1로 세팅을 한다.

그 후 for 문을 돌며 i번째 값은 i-1과 i-2값의 합으로 볼 수 있으므로 n까지 반복한다.

그 후 stairList의 n번째 인덱스 값이 결과 값이 된다.

 

class Solution:
   def climbStairs(self, n: 'int') -> 'int':
       if n == 1:
           return 1
       elif n == 0:
           return 1
       stairList = [0 for i in range(0, n+1)]
       stairList[0] = 1
       stairList[1] = 1
       for i in range(2, n+1):
           stairList[i] = stairList[i-1] + stairList[i-2]
       return stairList[n]

 

문제 출처 : https://leetcode.com/problems/climbing-stairs/

Climbing Stairs - LeetCode

Github : https://github.com/kkkkang1009/leetcode/blob/master/leetcode_70.py

GitHub - kkkkang1009/leetcode: leetcode