Dynamic Programming for MATLAB

Dynamic Programming has been implemented in MATLAB using two illustrative example
265 Downloads
Updated 29 Jan 2021

View Matlab Dynamic Programming on File Exchange

Matlab Dynamic Programming

Dynamic Programming has been demostrated by two examples:

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

Example 1: Fibonacci squence

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

  1. Fibo using Recursive method
  2. Fibo using Dynamic programming
  3. Fibo using Matrix Exponentiation (Fastest method)

MATLAB function

  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))

Example 2: Find number of path in the Grid Map with obstacles

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

  1. Count number of path using Recursive method
  2. Count number of path using Dynamic Programming

Usage:

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 = 475550
Elapsed time is 8.417751 seconds.

N2 = 475550
Elapsed time is 0.002251 seconds.

Contact

Email: smtoraabi@ymail.com

Cite As

mansour torabi (2024). Dynamic Programming for MATLAB (https://github.com/Mansourt/Matlab_Dynamic_Programming/releases/tag/v1.0), GitHub. Retrieved .

MATLAB Release Compatibility
Created with R2020b
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
Version Published Release Notes
1.0

To view or report issues in this GitHub add-on, visit the GitHub Repository.
To view or report issues in this GitHub add-on, visit the GitHub Repository.