Top Down Approach

Top-Down Approach in Dynamic Programming ::

Top-Down breaks the large problem into multiple subproblems.

if the subproblem solved already just reuse the answer.

Otherwise, Solve the subproblem and store the result.

Top-Down uses memorization to avoid re-computing the same subproblem again.

Let's solve the same Fibonacci problem using the top-down approach.

Top-Down starts breaking the problem unlike bottom-up.

Example :: 

If we want to compute Fibonacci(4), the top-down approach will do the following

Fibonacci(4) -> Go and compute Fibonacci(3) and Fibonacci(2) and return the results.

Fibonacci(3) -> Go and compute Fibonacci(2) and Fibonacci(1) and return the results.

Fibonacci(2) -> Go and compute Fibonacci(1) and Fibonacci(0) and return the results.

Finally, Fibonacci(1) will return 1 and Fibonacci(0) will return 0.

Here We are computing the result of Fib(2) two times.

This can be avoided using memorization.

Code is Given Below ::

#include<bits/stdc++.h>

using namespace std;

int dp[10005]; // For memorization

int fibonacci(int n)

{

if(n == 0 || n == 1)

return n;

if(dp[n] != -1)

return dp[n];

int result = fibonacci(n-1) + fibonacci(n-2);

return dp[n] = result;

}

int main()

{

int n;

cout << "Enter A Number :: ";

cin >> n;

cout << "\n";

memset(dp, -1, sizeof(dp)); // Its make dp array all index equal to -1

cout << "nth Fibonacci Number is :: ";

cout << fibonacci(n) << "\n";

}