Dynamic Time Warping recursive implementation
Question: Good evening ladies and gents,  
I want to implement a Dynamic Time Warping (DTW) algorithm in Python.

For testing purposes I set up a small random distance matrix (e.g., generated
by the Manhattan metric) and then call my DTW algorithm with it.

    
    
    import numpy as np
    from dynamic_time_warping import compute_dtw
    
    x=np.zeros((3,4))
    x[0,2]=1.0
    x[0,3]=2.0
    x[1,2]=1.0
    x[1,3]=2.0
    x[2,0]=1.0
    x[2,1]=1.0
    x[2,3]=1.0
    
    compute_dtw(x)
    

My DTW algorithm looks as follows:

    
    
    def compute_dtw(W):
        if W.shape[0]==1 or W.shape[1]==1:
            C=float("inf")
        if W.shape[0]==1 and W.shape[1]==1:
            C=0.0
        else:
            C=W[len(W),len(W)]+min(compute_dtw(W[0:-1, 0:-1]),
                compute_dtw(W[0:-1]), compute_dtw(W[:, 0:-1]))
        return C
    

I want the algorithm to take the m*n value of x and add it to the next minimum
value which I tried to achieve by calling the function again with a smaller
matrix. `(compute_dtw(W[0:-1, 0:-1]), compute_dtw(W[0:-1]), compute_dtw(W[:,
0:-1]))`

This gives me the following error after going once through the script:

> C=W[len(W),len(W)]+min(compute_dtw(W[0:-1, 0:-1]), compute_dtw(W[0:-1]),
> compute_dtw(W[:, 0:-1])) IndexError: index 3 is out of bounds for axis 0
> with size 3

Apparently, I am calling an element of the array that's not existent, but I
can't figure it out where it is breaking.

Thanks for your suggestions and help!

//updated code:

    
    
    def compute_dtw(W):
        if W.shape[0]==1 and W.shape[1]==1:
            C=0.0
        elif W.shape[0]==1 or W.shape[1]==1:
            C=float("inf")
        else:
            C=W[W.shape[0]-1,W.shape[1]-1]+min(compute_dtw(W[0:-1, 0:-1]), compute_dtw(W[0:-1]), compute_dtw(W[:, 0:-1]))
        return C
    


Answer: Python indexing starts at zero. On your first pass you calling for element
[3,3] (which does not exist) and the thus the out of bounds error.

I'm not all that familiar with dynamic time warping, but I think should be
using the `.shape` of the specific axis as opposed to the `len()` which is
just the length of the first dimension of your array. Even then, you'll have
to adjust your recursion to iterate over the bounds of each successive array.

Lastly, the `return` statement should be at the same level of the `if` blocks.
Currently, `compute_dtw` won't return anything in the first two cases, only if
the shape is greater than length 1 on both axes.

