[Algorithm] 70. Climbing Stairs 문제

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

Climbing Stairs - LeetCode

 

내 풀이

class Solution(object):
    def climbStairs(self, n):
        if n == 1:
            return 1
        d = [0] * (n)
        d[n-1] = 1
        d[n-2] = 2
        
        for i in range(n-3,-1,-1):
            d[i] = d[i+1] + d[i+2]
        return d[0]

 

 

개선한 풀이 (메모리 측면에서..)

이 문제는 결국 피보나치 수열하고 똑같은 문제다. 

배열 따로 선언해서 메모리 차지할 필요도 없이 변수 2개로 해결 가능

시간복잡도는 O(n) => 계속 memoization 하면 결국 모든 계산은 1번밖에 안 함

def climbStairs(n):
    one, two = 1, 1
    for i in range(n - 1):
        temp = one
        one = one + two
        two = temp
    return one