반복되는 부분 계산 줄이기
피보나치 수를 단순 재귀로 구하면 같은 작은 항을 여러 번 계산한다. 한 번 구한 값을 저장하면 이후에는 결과를 읽어 사용할 수 있다. 중요한 점은 저장 자체보다 어떤 부분 문제가 반복되는지 파악하는 데 있다.
상태에 필요한 정보
어떤 위치까지 왔는지만으로 이후 답을 정할 수 없는 문제도 있다. 남은 자원이나 이전 선택이 영향을 준다면 상태에 그 정보가 포함되어야 한다. 다른 상황을 같은 상태로 합치면 결과를 재사용해도 정답이 되지 않을 수 있다.
위에서 내려오거나 아래에서 쌓기
메모이제이션은 필요한 부분 문제를 재귀적으로 계산하면서 결과를 저장한다. 바텀업 방식은 의존하는 작은 상태부터 순서대로 계산한다. 둘 다 가능하더라도 실제로 방문하는 상태 수와 메모리 사용, 호출 비용은 달라질 수 있다.
빠르다는 보장은 별개
동적 계획법이라고 이름 붙였다고 모든 문제가 효율적으로 풀리는 것은 아니다. 상태 수가 너무 많거나 한 상태의 전이가 비싸면 계산량이 커진다. 먼저 상태 수와 전이 비용을 추정하고, 필요한 이전 결과만 남기는 메모리 최적화가 가능한지도 검토한다.