동적 계획법 연습 - 계단오르기(leetcode)

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

1칸 혹은 2칸씩 오를 수 있다면 n번째 칸에 이를 수 있는 방법은 몇 가지인지 구하기

bottom-up의 대표적인 예제! 

class Solution:
    def climbStairs(self, n: int) -> int:

        # bottom-up 으로 동적으로 기록해갈 배열
        dy = [0] * (n+1)
        # 작고 확실한 출발점
        dy[0] = 1
        dy[1] = 1
        # 전칸, 전전칸까지 올 수 있던 방법수를 합하여 해당 칸에 기록
        for i in range(2, n+1):
            dy[i] = dy[i-1] + dy[i-2]

        return dy[n]