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";
}
Comments
Post a Comment