[프로그래머스] 멀리뛰기: 점화식, dp

dp(동적프로그래밍)의 개념으로 접근해서 문제 푸는 방식 -> 하위 문제의 결과를 저장해서 같은 계산을 반복하지 않도록 함 (메모이제이션)

점화식: F(n)=F(n−1)+F(n−2)

 

const solution = (n) => {
    if (n === 1) return 1;
    if (n === 2) return 2;
    
    let dp = [0, 1, 2];
    
    for (let i = 3; i <= n; i++) {
        dp[i] = (dp[i - 1] + dp[i - 2]) % 1234567
    }
    
    return dp[n];
}

 

피보나치 수열과 유사 다른점은 초기 조건이 dp[2] = 1이 아니라 2인점