동적 계획법

• 분할 정복과 같은 접근방식을 의미
• 차이는 문제를 나누는 방식
• 동적계획법에서 어떤 부분 문제는 두 개 이상의 문제를 푸는 데 사용될 수 있기 대문에, 이 문제의 답을 여러 번 계산하는 대신 한 번만 계산하고 재활용하면서 속도 향상 -> 문제의 답을 메모리에 저장, 캐싱
• 함수의 결과를 저장하는 장소를 마련해두고 재활용하는 최적화 기법 = 메모이제이션
• 입력이 같으면 출력이 항상 같은 함수에만 메모이제이션을 적용할 수 있다
• 참조적 투명함수의 경우에만 메모이제이션이 적용 가능

1. 기저사례 먼저 체크
2. 캐시 값을 -1로 초기화(양수일 때만 가능)

시간복잡도 : 존재하는 부분 문제의 수 * 한 부분 문제를 풀 때 필요한 반복문 수행 횟수

푸는법

1. 완전탐색을 이용해 해결한다
2. 중복된 부분 문제를 한 번만 계산하도록 메모이제이션을 적용

와일드 카드

시간복잡도 : n 제곱 * 1 = n제곱

최적화 문제

최적 부분 구조 어떤 문제와 분할방식에 성립하는 조건 각 부분 문제의 최적해만 있으면 전체 문제의 최적해를 쉽게 얻어낼 수 있을 경우 이 조건이 성립

최적화 문제 동적 계획법 레시피

1. 완전 탐색 알고리즘 설계
2. 전체 답의 점수 반환이 아닌, 앞으로 남은 선택들에 해당하는 점수만을 반환하도록 부분 문제 정의 수정
3. 재귀 호출의 입력 이전의 선택과 관련된 정보가 있다면 필요한 것만 남기고 줄인다. 최적 부분 구조 성립 시 이전 선택 정보를 완전히 없앨 수도 있다. 우리이 목표는 가능한 한 중복되는 부분 문제를 많이 만드는 것이다. 입력의 종류가 줄수록 부분 문제의 중복이 많아지고, 메모이제이션을 최대한 활용 가능하다.
4. 입력이 배열이나 문자열인 경우 적절한 변환을 통해 메모이제이션
5. 메모이제이션 적용