Explain Memoization. How does it optimize recursive solutions?

Memoization is an optimization technique where the results of expensive function calls are cached (typically in a hash map or array keyed by input parameters), so that subsequent calls with the same inputs can return the cached result instead of recomputing it. It is a top-down approach to dynamic programming, applied directly on top of a recursive solution.

Memoization optimizes recursive solutions with overlapping subproblems by eliminating redundant computation. For example, naive recursive Fibonacci has O(2^n) time complexity because it recomputes fib(k) many times for the same k. By caching each computed fib(k), memoized Fibonacci reduces time complexity to O(n), at the cost of O(n) additional space for the cache.