Fibonacci Top Down Algorithm

The Fibonacci Top-Down Algorithm, also known as the memoization approach, is an optimization technique used to solve the classical Fibonacci sequence problem. In this method, the computational time is significantly reduced by storing the results of previously computed Fibonacci numbers and reusing them in subsequent calculations, as opposed to the traditional recursive algorithm, which suffers from repetitive calculations and exponential time complexity. By employing a top-down approach, the algorithm starts by solving a larger instance of the problem and then breaks it down into smaller subproblems, which are solved and their results stored in a cache (such as an array or dictionary) for future use. When the top-down algorithm computes the Fibonacci number for a given integer n, it first checks if the result has already been calculated and stored in the cache. If the result is available, the algorithm simply returns the cached value, avoiding any unnecessary computation. However, if the result has not been calculated, the algorithm proceeds to recursively compute the Fibonacci numbers for (n-1) and (n-2), and stores their results in the cache before returning the sum of these values as the final result. This memoization technique not only ensures that each Fibonacci number is computed only once, but it also significantly reduces the time complexity of the algorithm, making it an efficient and practical solution for solving the Fibonacci sequence problem.
#include <iostream>
using namespace std;
int arr[1000000];
int fib(int n)
{
	if (arr[n] == -1)
	{
		if (n <= 1)
			arr[n] = n;
		else
			arr[n] = fib(n - 1) + fib(n - 2);
	}
	return arr[n];
}
int main(int argc, char const *argv[])
{
	int n;
	cout << "Enter n: ";
	cin >> n;
	for (int i = 0; i < n + 1; ++i)
	{
		arr[i] = -1;
	}
	cout << "Fibonacci number is " << fib(n) << endl;
	return 0;
}

LANGUAGE:

DARK MODE: