Repository files navigation

Dynamic Programming has been demostrated by two examples:

1. Fibonacci sequence
2. Find number of path in the Grid Map with obstacles

Just run theFibonacci/EVAL_fibo.m file to compare run-time of the following three methods:

1. Fibo usingRecursive method
2. Fibo usingDynamic programming
3. Fibo usingMatrix Exponentiation (Fastest method)

1. Fibonacci/Fibo_R.m: Fibonacci with Recursive approach:

   • Time Complexity: O(2^n)
   • Space Complexity: O(2^n)

2. Fibonacci/Fibo_DP.m: Fibonacci with Dynamic programming (Memoization):

   • Time Complexity: O(n)
   • Space Complexity: O(n)

3. Fibonacci/Fibo_M.m: Fibonacci with Matrix Exponentiation:

   • Time Complexity: O(log(n))

Just run theGrid Path/EVAL_grid_path.m file to compare run-time of the following two methods:

1. Count number of path usingRecursive method
2. Count number of path usingDynamic Programming

clc,clear% Define Map (Grid Path)Map= zeros(15,10);Map(3,5)=1;Map(6,7)=1;Map(7,3)=1;% Visualize Map (Grid Path)MapView(Map)%%tic;N1= GridPath_R(Map,1,1)toc;tic;N2= GridPath_DP(Map,1,1)toc;

Grid map is as follows:

N1=475550Elapsedtime is 8.417751 seconds.N2=475550Elapsedtime is 0.002251 seconds.

Email:smtoraabi@ymail.com