DP 정리

Overlapping subproblem

• Problem을 작은 subproblem으로 분해
• subproblem의 계산값을 재사용

접근 방법

보통 문제를 풀 때 완전탐색으로 먼저 접근

1. 재귀(하위문제로 나누기 작업)
2. 반복문을 사용할 때 중복된 값이 나오면 계산결과를 (memo) 저장하여 재활용

DP 문제 풀이 정리

1. 일단 재귀함수로 비효율적인 완전탐색 코드를 작성한다.
2. 중복되는 subproblem의 계산 결과를 저장(memoize)한다.
3. 탑다운 , 바텀업 중 더 효율적인 것 선택.

DP 문제 예시 (탑다운, 바텀업)

Leetcode 746. Min Cost Climbing Stairs

1 step 또는 2 steps만 올라올 수 있으니까 subproblem으로 나누면

1층 아래에서 온 값과 + 1층까지 온 최소 값
2층 아래에서 온 값과 + 2층까지 온 최소 값

이 둘 중 더 작은 값을 가져오면 된다.

탑다운 (memo 이용한 재귀적 호출)

var minCostClimbingStairs = function(cost) {
    const memo = {};
    const length = cost.length;
    const dp = (n) => {
        if(n===0 || n===1) return 0;
        if(!(n in memo)){
            memo[n] = Math.min(dp(n-1)+cost[n-1],dp(n-2)+cost[n-2]);
        }
        return memo[n]
    }
    
    return dp(length);
};

바텀업 (반복문으로 계산결과 채우기)

var minCostClimbingStairs = function(cost) {
    const length = cost.length;
    const dp = Array(length+1).fill(0);
  	// dp의 길이가 0이나 1인 경우에는 0 반환필요
    for(let i=2;i<length+1;i++){
        dp[i] = Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
    }
    return dp[length]
};
};