프로그래머스(파이썬) - 멀리 뛰기

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

프로그래머스

처음에 문제보고 중복순열로 풀려고 하다가 .. 백트래킹도 생각해봤다가..

n을 1부터 증가해가며 확인해보니 간단하게 dp로도 풀 수 있었다.

문제에 적용할 알고리즘을 적절히 떠올리는게 너무 어려운 것 같다.

def solution(n):
    dp = [1, 1] + [0] * (n-1)
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n] % 1234567