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