[알고리즘] 멀리 뛰기

포인트

• 다이나믹 프로그래밍을 위한 문제임을 인지했습니다. 약간 너무 티가 난다고나 할까;;;;
• 1, 2 는 기본 케이스이면 이를 확장하면, 3을 만들기 위해서는 1, 2 가 필요합니다. 4를 만들기 위해서는 2, 3 이 필요합니다. 하지만 우리는 이미 2, 3 을 가지고 있습니다. 5를 만들기 위해서는 3, 4 가 필요합니다. 하지만 우리는 3과 4를 이미 구해왔습니다. 따라서 값을 바로 계산할 수 있습니다. 

🧶문서는 항상 수정될 수 있습니다. 비판은 환영합니다. 

python

def solution(n: int) -> int:
    d = [-1] * 2001
    d[1] = 1
    d[2] = 2
    for i in range(3, n + 1):
        d[i] = d[i - 1] % 1234567 + d[i - 2] % 1234567

    return d[n]