피보나치 수열의 응용 (Dynamic Programming)

                                    1 2 (기본형)
1 2 3 5 8 13 21 34 ...

                                    ✏️ DP가 필요한 환경인지 확인한다.
- 예를 들어 계단 오르기 처럼 한 방향으로 n칸씩 움직이는 문제와 같은 문제들이다.

✏️ map을 만든다.
각 점을 x좌표라고 생각하고 각 포인트마다 value를 가질 수 있도록 map을 구성한다.
{1: 1, 2: 2} 이런식이다.

✏️ 다음 결정은 map에서 참고한다.
다음 순서에 해당하는 값은 이전 value의 값들의 조합이다. map을 적극 활용하자.

                                    class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        stair = {1: 1, 2: 2}
        for i in range(3, n + 1):
            stair[i] = stair[i - 2] + stair[i - 1]

        return stair[n]