# Examples of Dynamic Programming with C++ and Matlab

In this tutorial, I will give you examples of using dynamic programming for solving the following problems:

1)Minimum number of coins for summing X.

2)The most (least) costly path on a grid (dynamic time warping).

3)Levenshtein edit distance.

4)Seam Carving. I have written a tutorial on that here and the recursive part is in the following lines:

The examples are taken from “Competitive Programmer’s Handbook” written by Antti Laaksonen.

# ROS packages for Dynamic Time Warping

Dynamic Time Warping (DTW) is a method to align two sequences under certain constraints. For instance, two trajectories that are very similar but one of them performed in a longer time. The alignment should be is such way that minimizes the distance between these two sequences. Here I have done DTW between two-time series with python. I found a good c++ library for Fast Dynamic Time Warping and I developed my wrapper to make a ROS package for that. Here you can download my code at GitHub.

The number of possible warping paths through the grid is exponentially explosive. The image is taken from [1].

A good wrapping function should have following characteristics:

• monotonicity: The alignment path does not go back in “time” index.

The image is taken from [1]

• continuity: The alignment path does not jump in “time” index.

The image is taken from [1]

• boundary conditions: The alignment path starts at the bottom left and ends at the top right.

The image is taken from [1].

• warping window: A good alignment path is unlikely to wander too far from the diagonal.

The image is taken from [1].

• slope constraint: The alignment path should not be too steep or too shallow.

The image is taken from [1].

• References: [1]

References: [1]

# Dynamic Time Warping with Python

Dynamic Time Warping (DTW) is a method to align two sequences such that they have minimum distance. For instance, two trajectories that are very similar but one of them performed in a longer time. Here is an example of my code with python. Here is my ROS package with C++ for DTW.

DTW applied two sinusoidal time series.

DTW applied two sinusoidal time series in the presence of noise