[LeetCode] 70. Climbing Stairs

접근

• 처음 DFS로 풀이 시도
• 허나 도식화 후 Memoization이 가능함을 보고 DP로 솔루션 작성이 가능함을 판단
• DP 방식 중 Top Down 으로 푸는 방법이 도저히 생각이 나지 않아 Bottom-up으로 고민 후 솔루션 작성
• DP의 가장 교과서적인 문제 중 하나... 알고리즘 수업 때도 보았던 문제로 기억남

 

문제 링크

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

 

솔루션

class Solution:
    def climbStairs(self, n: int) -> int:
        DP = [1 for _ in range(n+1)]
        
        # Bottom-up
        for i in range(n-2, -1, -1):
            DP[i] = DP[i+1] + DP[i+2]

        return DP[0]

 

아래 유투브 영상을 참고해주세요. 이 문제를 접근하는 흐름에 대해 아주 잘 알려줍니다.