Clibing Stairs

문제

• n개의 계단
• 한 번에 1 or 2 계단 오름
• 중복되지 않는 계단을 오르는 방법 수

풀이

dp 문제라는 걸 알고 시작해서 어렵지 않을 것 같다..
n개의 리스트를 만들고
list[i]에 list[i-1]+list[i-2]를 넣는다.
1칸 전과 2칸 전의 계단을 밟은 경우의 수를 합산하여 구하는 것
list[0] = 1, list[1] = 1를 기본으로 주고 시작

class Solution:
    def climbStairs(self, n: int) -> int:
        stairs = [0 for _ in range(n+1)]
        stairs[0] = 1
        stairs[1] = 1
        for i in range(2, n+1):
            stairs[i] = sum(stairs[i-2: i])
        return stairs[-1]

결과

혹시 시간을 줄일 수 있을까 싶어서, 리스트 대신 int 만 저장해봤는데 큰 차이는 없었다.

class Solution:
    def climbStairs(self, n: int) -> int:
        one = 1
        two = 1
        three = 1
        for i in range(2, n+1):
            three = one+two
            one, two = two, three
        return three