DP(Dynamic Programming) 주어진 문제를 하위 문제로 나누고, 작은 문제들부터 시작하여 점점 큰 문제를 해결하는 상향식(Bottom-Up) 방식 배열이나 테이블에 작은 하위 문제의 결과를 저장하고, 각 단계에서 이를 참조하여 더 큰 문제를 해결한다. 작은 문제들을 차례로 해결하여 마지막에 전체 문제의 해답을 얻는 방식 장점모든 하위 문제를 한 번씩만 계산하고 결과를 저장하므로 재귀 호출의 깊이에 제한이 없어 메모리 오버헤드가 적고, 대부분의 경우 실행 속도 역시 바르다. 한계해결해야 할 모든 하위 문제를 미리 테이블에 저장하므로 불필요한 계산과 메모리 낭비가 발생할 수 있다. 메모이제이션(Memoization) 필요할 때만 하위 문제를 해결하고 이를 캐시에 저장하는 방식 재귀적으로 문제를..