liveBook · Manning

Memoization

As explained in Timeless Algorithms, The Foundational Ideas

Memoization is a dynamic-programming implementation technique that recursively evaluates only needed subproblems and caches their computed values.

Memoization is a top-down dynamic-programming technique: begin with the original problem, recursively evaluate only the needed subproblems, and retain computed results for reuse. section 6.1.4 section 10.2.5

It evaluates the same recurrence, states, transitions, and base cases as tabulation; the methods differ in the order subproblems are encountered and stored. section 6.1.4

Multistage network optimization

A recurrence combines each choice’s immediate cost with the best outcome from the next state. Memoization can retain evaluated subproblems; with optimal substructure and exact evaluation, their solutions yield a global optimum. section 10.2.5

Its computational benefit depends on overlapping subproblems. Without optimal substructure, the global guarantee fails; without repeated subproblems, storing results offers little benefit. section 10.2.5

How Timeless Algorithms, The Foundational Ideas covers it

How deep it goes
Explains memoization’s top-down role and optimization assumptions, without providing a worked memoization trace.
Examples
Uses multistage network optimization to illustrate recurrence-based decomposition and reuse of subproblem results.
What it assumes
Assumes a specified recurrence and state structure, with optimal substructure and overlapping subproblems supporting dynamic programming.
What you can do after
Apply memoization to evaluate a recurrence exactly when optimal substructure holds, reusing results from overlapping subproblems.
How it connects
Links memoization to dynamic programming, recurrence relations, tabulation, optimal substructure, and overlapping subproblems.

Also explained in

Compare how 9 books explain memoization →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Timeless Algorithms, The Foundational Ideas. The section links point to the parts of the book it draws on.