Dynamic Programming vs Memoization

Memoization means the optimization technique where you memorize previously computed results, which will be used whenever the same result will be needed.

Dynamic programming (DP) means solving problems recursively by combining the solutions to similar smaller overlapping subproblems, usually using some kind of recurrence relations.

Nowadays I would interpret "dynamic" as meaning "moving from smaller subproblems to bigger subproblems". (The word "programming" refers to the use of the method to find an optimal program, as in "linear programming". People like me treat it as in software programming sometimes)

In summary, here are the difference between DP and memoization.

  • DP is a solution strategy which asks you to find similar smaller subproblems so as to solve big subproblems. It usually includes recurrence relations and memoization.
  • Memoization is a technique to avoid repeated computation on the same problems. It is special form of caching that caches the values of a function based on its parameters.

Memoization is the technique to "remember" the result of a computation, and reuse it the next time instead of recomputing it, to save time. It does not care about the properties of the computations.

Dynamic programming is the research of finding an optimized plan to a problem through finding the best substructure of the problem for reusing the computation results. In other words, it is the research of how to use memoization to the greatest effect.

The name "dynamic programming" is an unfortunately misleading name necessitated by politics. The "programming" in "dynamic programming" is not the act of writing computer code, as many (including myself) had misunderstood it, but the act of making an optimized plan or decision.

The earlier answers are wrong to state that dynamic programming usually uses memoization. Dynamic programming always uses memoization. They make this mistake because they understand memoization in the narrow sense of "caching the results of function calls", not the broad sense of "caching the results of computations".