Swift) 프로그래머스 멀리뛰기 - Lv. 2

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

프로그래머스

문제 풀이: 처음에는 dfs방식으로 문제를 풀었지만 잘 안되서 피보나치와 비슷하다는 문제인 걸 알아서 dp로 문제를 해결. dp[n]은 n번째 위치에 있을때 마지막까지 갈 수 있는 방법의 수를 의미한다.

var dp: [Int] = Array(repeating: 0, count: 2002)

func solution(_ n:Int) -> Int {
    dp[0] = 0
    dp[1] = 1
    dp[2] = 2
    if n == 1 {
        return 1
    }
    if n == 2 {
        return 2
    }
    for i in 3...n {
        dp[i] = (dp[i-1] + dp[i-2]) % 1234567
    }
    return dp[n]
}