ExiiS 프로그래밍 저장소

https://stackoverflow.com/questions/6184869/what-is-the-difference-between-memoization-and-dynamic-programming

Q.

What is the difference between memoization and dynamic programming? I think dynamic programming is a subset of memoization. Is it right?

Memozation과 DP의 차이점이 무엇인가요? DP가 memoization에 포함되어있는 것 같은데, 맞죠?

A.

Memoization is a term describing an optimization technique where you cache previously computed results, and return the cached result when the same computation is needed again.

Dynamic programming is a technique for solving problems of recursive nature, iteratively and is applicable when the computations of the subproblems overlap.

Dynamic programming is typically implemented using tabulation, but can also be implemented using memoization. So as you can see, neither one is a "subset" of the other.

Memozation은 이전에 계산한 결과를 캐싱하고, 또다시 같은 계산을 해야할 때 그 캐시를 리턴하는 방식의 기술적 최적화를 설명하는 용어 입니다.

DP는 반복 혹은 재귀적인 성격의 문제를 푸는 테크닉입니다. 또한 하위 문제의 계산이 오버랩(겹쳐짐, 반복)된다면 적용 될 수 있습니다.

DP는 일반적으로 테이블을 작성하여 구현되나, memoization을 사용하여 구현할 수도 있습니다. 따라서 보시다싶이 어느 한쪽도 다른쪽의 "subset"이 아닙니다.

A reasonable follow-up question is: What is the difference between tabulation (the typical dynamic programming technique) and memoization?

When you solve a dynamic programming problem using tabulation you solve the problem "bottom up", i.e., by solving all related sub-problems first, typically by filling up an n-dimensional table. Based on the results in the table, the solution to the "top" / original problem is then computed.

If you use memoization to solve the problem you do it by maintaining a map of already solved sub problems. You do it "top down" in the sense that you solve the "top" problem first (which typically recurses down to solve the sub-problems).

이후 나올법 한 질문 : tabulation(DP에서 사용하는)과 memoization 간의 차이점이 무엇인가요?

tabulation을 사용하여 DP 문제를 푼다면 "Bottom UP", 즉 일반적으로 n차원 테이블을 채워나가며 관련된 모든 하위 문제를 먼저 품으로 문제를 푸는 것입니다. 테이블의 결과를 기반으로 최상위(top)/원래 문제에 대한 솔루션이 계산됩니다.

만약 문제를 풀기 위해 memoization을 사용했다면 이미 푼 하위 문제의 map을 maintaning(유지보수)하며 풀 수 있습니다.

(즉 이전 값을 활용하여 다음 문제의 값을 구한다는 의미)

"top down"은 상위 문제를 먼저 푼다는 의미에서 수행할 수 있습니다.