70. Climbing Stairs

https://leetcode.com/problems/climbing-stairs/submissions/

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

al, bl, cl 빈 배열을 만들고, count를 초기화한다.
2steps와 1step이 최대 몇개 들어갈 수 있는지 확인하여 0부터 최대개수까지 al과 bl에 append한다.

결국 n은 2a + b의 형태가 되어야 하기에 그에 맞는 쌍들을 al과 bl에서 뽑아 cl에 튜플로 집어 넣는다.

그리고 cl을 순회하며 중복순열 공식을 이용해 경우의 수를 구한다.

그 경우의 수를 count에 저장하여 리턴한다.

import math

class Solution:
    def climbStairs(self, n: int) -> int:
        al = []
        bl = []
        cl = []
        count = 0

        for i in range(n//2+1):
            al.append(i)

        for i in range(n+1):
            bl.append(i)

        for a in al:
            for b in bl:
                if 2*a + b == n:
                    cl.append((a,b))

        for x, y in cl:
            if x and y != 0:
                count = int(count + (math.factorial(x+y) / (math.factorial(x) * math.factorial(y))))
            else :
                count += 1

        return count