복잡한 문제를 작은 하위 문제로 나누고,
그 결과를 재사용해 문제 해결하는 기법이다
최적화 이론의 한 기술
큰 문제를 풀기 위해 같은 하위 문제를 반복해서 계산하게 되는 구조
이 중복 계산을 피하기 위해 결과를 저장(메모이제이션)
전체 문제의 최적해가 부분 문제들의 최적해로 구성
작은 문제를 잘 풀면 큰 문제도 최적의 해
하위 문제의 계산 결과를 저장해두고 다시 사용할 수 있어야 한다.
메모이제이션: 필요할 때 계산하고 저장 (Top-Down)
테이블 기반: 미리 계산해서 저장 (Bottom-Up)