[Algorithm] DP 동적 계획법

• 재귀와 DP의 차이
  • 재귀는 하향식 접근
  • DP는 상향식 접근, 계산 결과를 저장하는 memoization 사용
• DP 사용
  • 문제의 최적 결과를 낼 때
  • 동일한 작은 문제들이 반복하여 나타나는 경우
  • 작은 문제를 풀고 memoization 하면서 전체 문제 해결

 

class DP {
    public int solution(int[] arr) {
        int len = arr.length;

        if(len == 0) {
            return 0;
        } else if (len == 1) {
            return arr[0];
        }

        int[] answer = new int[len];
        
        answer[0] = arr[0];
        answer[1] = Math.max(arr[0], arr[1]);

        for(int i = 2; i < len; i++) {
            answer[i] = Math.max(answer[i - 1], answer[i - 2] + arr[i]);
        }

        return answer[len - 1];
    }
}