Memoization is a technique used in dynamic programming to optimize the performance of recursive algorithms by caching the results of expensive function calls and returning the cached result when the same inputs occur again. It is a top-down approach to solving problems, where the problem is broken down into smaller subproblems, and the results of each subproblem are stored for future reference.

Here's how memoization works:

1. Function Definition:

   • The original function is modified to include a cache, typically implemented as a dictionary or an array.
   • The cache stores the results of previously computed subproblems.

2. Cache Lookup:

   • Before computing the result for a subproblem, the function checks if the result is already available in the cache.
   • If the result is found in the cache (a cache hit), the cached value is returned, avoiding redundant calculations.

3. Recursive Calls:

   • If the result is not found in the cache (a cache miss), the function proceeds with the recursive calls to solve the subproblem.
   • The recursive calls break down the problem into smaller subproblems until a base case is reached.

4. Cache Storage:

   • After computing the result of a subproblem, the function stores the result in the cache using the input parameters as the key.
   • This allows the cached result to be reused when the same subproblem is encountered again.

5. Return Value:

   • The function returns the computed or cached result to the caller.

By memoizing the results of subproblems, the algorithm avoids redundant calculations and significantly improves the runtime performance. Memoization is particularly effective when the subproblems overlap and are solved repeatedly.

Here's a simple example of memoization applied to the Fibonacci sequence:

def fibonacci(n, memo=None):
    if memo is None:
        memo = {}

    if n in memo:
        return memo[n]

    if n <= 1:
        return n

    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]

In this example, the fibonacci function uses memoization to store the results of previously computed Fibonacci numbers. The memo dictionary acts as the cache. Before computing the Fibonacci number for a given n, the function checks if the result is already in the cache. If it is, the cached value is returned. Otherwise, the function proceeds with the recursive calls and stores the computed result in the cache for future reference.

Memoization can greatly reduce the time complexity of recursive algorithms, especially those with overlapping subproblems. It eliminates redundant calculations by reusing previously computed results, leading to a more efficient solution.

However, memoization does come with a trade-off in terms of space complexity. The cache used to store the results of subproblems requires additional memory. The space complexity depends on the number of unique subproblems that need to be stored.

Memoization is a powerful technique in dynamic programming and can be applied to a wide range of problems, including optimization problems, counting problems, and decision problems. It is particularly useful when the recursive solution has overlapping subproblems and exhibits optimal substructure.