Dynamic programming

20.1 - DP Fibonacci

The pure recursive Fibonacci function from the Recursive Fibonacci lesson results in exponential number of calls. We can avoid duplicate call by using memoization, which results in linear number of calls.

Memoization works by storing the value already computed in a memo. The memo can be made using a vector, a map, an unordered_map, etc. When a previously computed value is needed, repeat calculation can be avoided by using the value in the memo.

Task

Define the function int fibonacci(int n, std::vector &memo) which gives the nth Fibonacci number by using recursion and memoization.

  • Start with the recursive Fibonacci function.
  • Other than the base case, check if the value exists in the memo or not:
    • If it exists, then use the memo value.
    • If it does not exist, compute it and put the result in the memo.
#include <iostream> #include <vector> int fibonacci(int n, std::vector<int> &memo) { // Define this function. } int main() { int n{}; std::cin >> n; // Memo definition, initialized to contain n + 1 integers. std::vector<int> memo(n + 1, 0); std::cout << fibonacci(n, memo) << std::endl; }

20.1 - DP Fibonacci