Memoization

Memoization is a technique used in dynamic programming to improve the performance of recursive solutions by caching previously computed results. It involves storing the results of expensive function calls and returning the cached result when the same inputs occur again.

With memoization, we avoid redundant calculations by storing the results of subproblems in a data structure, such as a hash map or an array. This allows us to retrieve the result in constant time, rather than recomputing it.

Memoization can be particularly useful when solving recursive problems with overlapping subproblems, such as the Fibonacci sequence. Let's take a look at an example:

1#include <iostream>
2#include <unordered_map>
3
4int fib(int n, std::unordered_map<int, int>& memo) {
5    if (memo.find(n) != memo.end()) {
6        return memo[n];
7    }
8    
9    if (n <= 1) {
10        return n;
11    }
12    
13    int result = fib(n-1, memo) + fib(n-2, memo);
14    memo[n] = result;
15    return result;
16}
17
18int main() {
19    int n = 10;
20    std::unordered_map<int, int> memo;
21    int result = fib(n, memo);
22    std::cout << "The Fibonacci number at position " << n << " is " << result << std::endl;
23    return 0;
24}

In this example, we calculate the Fibonacci sequence using memoization. The function fib takes an integer n and a hash map memo to store the results. If the result for n has already been computed and stored in memo, we retrieve it directly. Otherwise, we calculate the result recursively and store it in memo for future use.

By using memoization, we eliminate redundant calculations and improve the time complexity of computing the Fibonacci sequence from exponential to linear. Memoization is a powerful technique that can significantly optimize recursive algorithms and is a key concept in dynamic programming.

xxxxxxxxxx

#include <iostream>

#include <unordered_map>

​

int fib(int n, std::unordered_map<int, int>& memo) {

    if (memo.find(n) != memo.end()) {

        return memo[n];

    }

    if (n <= 1) {

        return n;

    }

    int result = fib(n-1, memo) + fib(n-2, memo);

    memo[n] = result;

    return result;

}

​

int main() {

    int n = 10;

    std::unordered_map<int, int> memo;

    int result = fib(n, memo);

    std::cout << "The Fibonacci number at position " << n << " is " << result << std::endl;

    return 0;

}