[프로그래머스] 멀리 뛰기

문제 링크:

https://school.programmers.co.kr/learn/courses/30/lessons/12914

회고

• 동적 프로그래밍(Dynamic Programming, DP) 알고리즘 유형에 속함.
• DP는 복잡한 문제를 간단한 여러 개의 하위 문제로 나누어 해결하는 방식.
• 각 하위 문제의 해결 결과를 저장해두었다가, 같은 하위 문제가 다시 등장할 때 재계산하는 대신 저장된 결과를 재사용함으로써 계산 시간을 대폭 줄이는 방법.
• 예를 들어, 아래 문제의 경우 한 번에 1칸 혹은 2칸을 뛸 수 있으므로, 3칸에 도달할 경우의 수는 "1칸에 도달하는 경우의 수" + "2칸에 도달하는 경우의 수"가 된다.
  
  

python

def solution(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    else:
        dp = [0] * (n + 1)
        dp[1] = 1
        dp[2] = 2

        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]

        return dp[n] % 1234567