Dynamic Programming is a method for solving a complex problem by breaking it down to collection of simpler sub problems, and solving each of those sub problems just once and storing the solution using a memory based data structure (array, list, queue, stack, map, etc.,). So, when the next time the same problem occurs instead of recomputing, it has been taken from the memory to reduce the computation time.
There is a fancy way to define Dynamic Programming "Remembering stuff to save time later". Even this blog is also created for the same.
Remember that dynamic programming is all about getting sub problems.
Click here to understand Fibonacci Numbers.
To compute Fibonacci Number of 6, we need to add F(5) & F(4). Again, adding previous Fibonacci numbers is mandatory to compute the F(5) and this list goes till we reach F(0). This means we will eventually compute, all previous Fibonacci numbers of the given number.
There are two types of implementation in dynamic programming for memorisation.
1. Top-Down version
2. Bottom-Up version
Top-Down Version
<to be updated>
Bottom-Up Version
Instead of computing the Fibonacci number from the given number, if we compute it from 0, it is called Bottom-Up version.
The below algorithm can be found here to run/debug.
Algorithm/Pseudocode
int findFinbonacciNumber(num) { int f[num] = {0}; int i = 2; f[0] = 0, f[1] = 1; while (i <= num) { f[i] = f[i-1] + f[i-2]; i++; } return f[num]; }
Executable Program
#include <iostream> using namespace std; int findFibonacciNumber(int num) { int f[num] = {0}; int i = 2; f[0] = 0, f[1] = 1; while (i <= num) { f[i] = f[i-1] + f[i-2]; i++; } return f[num]; } int main() { int res = findFibonacciNumber(6); cout << res << endl; return 1; }
Remember: Check if the given problem is 1D or 2D which is very much important.
I splited the dynamic programming problems into categories:
Comments
Post a Comment