동적 프로그래밍 (DP, Dynamic Programming)

 * 동적 프로그래밍 (DP, Dynamic Programming)

이미 계산한 결과를 저장해 두었다가 필요할 때 다시 사용하는 방식
위의 개념을 메모이제이션 (Memoization)이라고 한다

복잡한 문제를 더 간단한 하위 문제로 나누어 품

동적 프로그래밍 키워드는
 1. 비슷한 문제는 반복해서 풀지 않음
 2. 한번 푼 것은 기억해서
 3. 필요할 때 재활용

..~~~~..

 * 동적 프로그래밍의 조건

 1. 중복되는 하위 문제 (Overlapping Subproblems)
큰 문제를 푸는 과정에서, 같은 하위 문제가 여러번 반복되어 등장

 2. 최적 부분 구조 (Optimal Substructure)
문제의 정답이 하위 문제의 정답으로부터 쉽게 구성

..~~~~..

 * 동적 프로그래밍 구현 방식

 1. Top-Down
필요할 때 계산하는 방식

재귀 + 메모이제이션 사용
큰 문제 -> 작은 문제로 분할

간단하고 이해하기 쉬움
but, 재귀 깊이가 깊으면 -> 스택 오버플로우 문제 있음


 2. Bottom-Up
처음부터 모든 경우를 계산하는 방식

반복문 + 테이블(주로 배열) 사용
작은 문제로부터 시작해서 -> 큰 문제 해결

시간, 공간 자원 사용이 적다

..~~~~..

 * 동적 프로그래밍으로 푸는 방법

 1. 상태 정의 필요 (State)
dp[index]는 index까지 계산했을 때의 최적 결과를 의미한다

 2. 점화식 설계 (Recurrence Relation)

 3. 초기 조건을 명확히 설정 (Base Case)

..~~~~..

 * 배열 크기 주의할 점

점화식에서 접근하는 최대 인덱스보다 배열의 크기가 커야 한다

Math.max()를 이용해서 배열의 크기를 정하도록 하자
int [] dp = new int [Math.max()]

..~~~~~..