[algo] DP

DP는 언제 사용할까?

1. 피보나치
2. 배낭 문제 (Knapsack Problem): 제한된 무게 안에서 아이템의 가치를 최대로 하는 문제.
3. 최대 부분 수열 합 (Maximum Subarray Sum): 연속된 배열 요소의 합이 가장 큰 경우를 찾는 문제.
4. 문자열 관련 문제: 예를 들어, 두 문자열의 최소 편집 거리(Levenshtein distance) 계산.
5. 경로 찾기 문제: 특정 격자에서 출발지에서 목적지까지 가는 경로의 경우의 수 계산.

DP로 피보나치 풀어보기

function fibDP(n, memo = {}) {
    if (n <= 1) return n;
    if (memo[n]) return memo[n]; // 이미 계산된 값이 있으면 반환
    memo[n] = fibDP(n - 1, memo) + fibDP(n - 2, memo); // 계산 후 저장
    return memo[n];
}
console.log(fibDP(10)); // 55

function fibBottomUp(n) {
    if (n <= 1) return n;
    
    let dp = [0, 1]; // 초기 값
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}
console.log(fibBottomUp(10)); // 55