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인점
728x90